In the last lecture, we reduced the problem of cheating in (the k-times repeated m-cycle game) to finding a small set of edges in whose removal eliminates all topologically non-trivial cycles. Such a set is called a spine. To get some intuition about how many edges such a spine should contain, let’s instead look at a continuous variant of the problem.
Spines, Foams, and Isoperimetry
Consider again the -dimensional torus , which one can think of as with opposite sides identified. Say that a nice set (e.g. a compact, surface) is a spine if it intersects every non-contractible loop in . This is the continuous analog of a spine in . We will try to find such a spine with surface area, i.e. , as small as possible.
Let’s consider some easy bounds. First, it is clear that the set
is a spine with . (A moment’s thought shows that this is “equivalent” to the provers playing independent games in each coordinate of .)
To get a good lower bound, it helps to relate spines to foams which tile according to , as follows. Take two potential spines.
To determine which curve is actually a spine, we can repeatedly tile them side-by-side.
The first tiling contains the blue bi-infinite curve, which obviously gives a non-trivial cycle in , while the second yields a tiling of by bodies of volume 1. It is easy to deduce the following claim.
Claim: A surface is a spine if and only if it induces a tiling of the plane by bodies of volume 1 which is invariant under shifts by .
By the isoperimetric inequality in , this immediately yields the bound
where is the unit -dimensional sphere.
So the the surface area of an optimal spine lies somewhere between and . On the one hand, cubes tile very nicely but have large surface area. On the other hand, we have sphere-like objects which have small surface area, but don’t seem (at least intuitively) to tile very well at all. As first evidence that this isn’t quite right, note that it is known how to cover by disjoint bodies of volume at most 1 so that the surface area/volume ratio grows like . See Lemma 3.16 in this paper, which is based on Chekuri, et. al. It’s just that these covers are not invariant under shifts.
Before we reveal the answer, let’s see what consequences the corresponding discrete bounds would have for parallel repetition of the m-cycle game. If the “cube bound” were tight, we would have , which doesn’t rule out a strong parallel repetition theorem ( in the previous lecture). If the “sphere bound” were tight, we would have , which shows that . In the latter case, the approach to proving equivalence of the UGC and MAX-CUT conjectures doesn’t even get off the ground.
As the astute reader might have guessed, recently Ran Raz proved that for some constant , showing that a strong parallel repetition theorem—even for unique games—is impossible. Subsequently, Kindler, O’Donnell, Rao, and Wigderson showed that there exists a spine with . While it is not difficult to show that the continuous result implies Raz’s discrete result, we will take a direct approach found recently by Alon and Klartag.