Communications - October 2012

toward such a strong theorem, first to f (d) ≥ d1/3 15 in general, and then to f (d)≥ 22 for an important subclass of constraints satisfaction problems, but the progress stopped at .

Feige et al. 11 were the first to observe that the parallel repetition question was related to foams. They studied a particular collection of constraints called Odd Cycle constraints, and showed that for them f (d) ≥ . They also showed that if there is a d-dimensional cubical foam with surface area A(d), then for this constraint satisfaction problem f (d) ≤ A(d). In particular, this meant that any proof that improved on their bound would show that there is no cubical foam with surface area , and any Strong Parallel Repetition theorem would prove that standard cubes are essentially the best cubical foams.

Once again, Raz24 resolved the matter and showed that Odd Cycles were a counterexample to Strong Parallel Repetition. He proved that for Odd Cycle constraints f (d) ≤ and thus that the results of bounds f (d)≥ of Feige et al. 11 and Rao22 are optimal! Indeed, one can view Raz’s work as constructing a discrete cubical foam, with surface area proportional to . A key tool used by Raz was the so-called Consistent Sampling Lemma, invented by Holenstein to prove the upper bound of f (d) ≤ d1/3 mentioned above. Raz’s result inspired our construction.

2. An ALGoRithm FoR BuiLDinG CuBiCAL FoAmS

Our solution to the Cubical Foam Problem involves generalizing Raz’s discrete methods to Euclidean space and opening up the proof of the Consistent Sampling Lemma. We use the “Buffon’s Needle” method to estimate surface area and we optimize our results using Fourier analysis.

Before describing our “sphere-like” cubical foam, we give some motivation for its construction. As stated earlier, our construction can also be interpreted as a very noise-resistant randomized discretization procedure for rounding off vectors of real numbers to vectors of integers.

Definition 1. A discretization is a mapping which assigns each point x = (x1,…, xd) ∈ Rd to an integer point r = (r1,…, rd) ∈ Zd, such that |ri − xi| < 1 for each i. If a discretization has the property that whenever x is rounded to r, then x + s is rounded to r + s for all s ∈ Zd, we say that the discretization is periodic. Given a periodic discretization, we define its principle bubble to be the set of points that are rounded to the origin.

The principal bubble of a periodic discretization tiles Rd
according to the integer lattice. Thus, any periodic discreti-
zation immediately yields a cubical foam. We will in fact
give a randomized procedure whose output is a periodic
discretization (hence also a cubical foam). As described
earlier, we say that such a procedure is noise-resistant if
every two nearby points x, y ∈ Rd are unlikely to be assigned
to different integer points. Intuitively, we expect the bub-
bles produced by a noise-resistant procedure to have
small surface area, because x and y are assigned to differ-
ent integer points only if the line segment joining them
crosses the surface of a bubble. We will later see that find-
ing a periodic discretization in which nearby pairs x and y
are usually assigned to the same integer point is very similar
to a constraint satisfaction problem where every constraint
involves two variables which are points in Rd. Indeed, Raz’s
analysis of the Odd Cycle constraints suggests the investiga-
tion of a related problem (which we state somewhat impre-
cisely for the sake of brevity): Assign each point x in the unit
cube [0, 1)d a shift z ∈ [0, 1)d in such a way that most nearby
pairs of points are likely to be assigned the same shift.