Monstrous Branes

 We study D-branes in the bosonic closed string theory whose automorphism group is the Bimonster group (the wreath product of the Monster simple group with ℤ₂). We give a complete classification of D-branes preserving the chiral subalgebra of Monster invariants and show that they transform in a representation of the Bimonster. Our results apply more generally to self-dual conformal field theories which admit the action of a compact Lie group on both the left- and right-moving sectors. Received: 20 February 2002 / Accepted: 17 August 2002 Published online: 19 December 2002 Communicated by R.H. Dijkgraaf     

On Donaldson’s flow of surfaces in a hyperkähler four-manifold

We prove some basic properties of Donaldson’s flow of surfaces in a hyperkähler 4-manifold. When the initial submanifold is symplectic with respect to one Kähler form and Lagrangian with respect to another, we show that certain kinds of singularities cannot form, and we prove a convergence result under a condition related to one considered by M.-T. Wang for the mean curvature flow.     

Robust locally testable codes and products of codes

We continue the investigation of locally testable codes, i.e., error‐correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of robust probabilistically checkable proofs, we introduce the notion of robust local testability of codes. We relate this notion to a product of codes introduced by Tanner and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low‐degree multivariate polynomials (which are a special case of tensor codes). Combining these two results gives us a generic construction of codes of inverse polynomial rate that are testable with poly‐logarithmically many queries. We note that these locally testable tensor codes can be obtained from any linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Improved bounds for sampling contingency tables

We study the problem of sampling contingency tables (nonnegative integer matrices with specified row and column sums) uniformly at random. We give an algorithm which runs in polynomial time provided that the row sums r_i and the column sums c_j satisfy r_i = Ω(n^3/2m log m), and c_j = Ω(m^3/2n log n). This algorithm is based on a reduction to continuous sampling from a convex set. The same approach was taken by Dyer, Kannan, and Mount in previous work. However, the algorithm we present is simpler and has weaker requirements on the row and column sums. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 135–146, 2002