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.
Algorithm 1: periodic discretization (and foam) construction,
given f:
1. Let all points of Rd be unassigned.
2. For stage i = 1, 2, … until all points are assigned:
(a) Choose a uniformly random pair (Zi, Hi) from [0, 1)d
× (0, f ∞).
(b) Let droplet Di be {x :
boundary.
(c) Assign all currently unassigned points in Di to (0,…, 0),
and extend this assignment periodically.
(d) Color all assignments from stage i with color i.
(x)> Hi}, together with its
We remark that we color all the assignments merely to aid in
the analysis of the algorithm.