No frills proof of higher-order Cheeger inequality

Following some recent applications by Mamoru Tanaka and Laurent Miclo, I was asked where there is a short, no-frills, self-contained, and (possibly) quantitatively non-optimal proof of the higher-order Cheeger inequalities from our paper with Shayan Oveis-Gharan and Luca Trevisan. I thought I would post it here. (If you’re hungering for something new, see this recently posted preprint of my coauthors relating higher eigenvalues to graph expansion.)

[Update: The application of Miclo can also be done using the higher-order Cheeger inequalities of Louis, Raghavendra, Tetali, and Vempala.]

The main simplification comes from doing the random partitioning non-optimally with axis-parallel cubes. For ease of notation, we will deal only with regular graphs, but there will be no quantitative dependence on the degree and this assumption can be removed (see the full paper).

Suppose that {G=(V,E)} is a connected, {n} -vertex, {d} -regular graph. Define the Laplacian by {\mathcal L = I - (1/d)A} , where {A} is the adjacency matrix of {G} . We will think of {\mathcal L} as acting on {\ell^2(V)} , the space of functions {f : V \rightarrow \mathbb R} equipped with the {\ell^2} norm. {\mathcal L} is positive semi-definite with spectrum

\displaystyle  0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_{|V|} \leq 2\,.

We we define the Rayleigh quotient of a function {f \in \ell^2(V)} by

\displaystyle  \mathcal R(f) = \frac{\sum_{u \sim v} (f(u)-f(v))^2}{d \sum_{u \in V} f(u)^2}\,,

where the numerator is summed over edges of {G} . By the variational principle for eigenvalues, we have

\displaystyle  \lambda_k = \min_{\stackrel{W \subseteq \ell^2(V)}{\dim(W)=k}} \max_{0 \neq f \in W} \mathcal R(f)\,. \ \ \ \ \ (1)

For a subset {S \subseteq V} , we define the expansion of {S} by {\phi(S) = \mathcal R(\mathbf{1}_S)} , where {\mathbf{1}_S} is the indicator function of {S} .

Finally, for {k \in \{1,2,\ldots,n\}} , we define the {k} -way expansion constant of {G} by

\displaystyle  \rho_G(k) = \min \left\{ \max_i \phi(S_i) : S_1, S_2, \ldots, S_k \subseteq V \right\}\,,

where the minimum is over collections of {k} disjoint, non-empty subsets of {V} .

The classical discrete Cheeger inequality asserts that

\displaystyle  \frac{\lambda_2}{2} \leq \rho_G(2) \leq \sqrt{2\lambda_2}\,.

We will now prove the following generalization. See the full paper for a discussion of the surrounding issues and better quantitative bounds.

Theorem 1 For every {k \in \{1,2,\ldots,n\}} ,

\displaystyle  \frac{\lambda_k}{2} \leq \rho_G(k) \leq 30 k^{3.5} \sqrt{\lambda_k}\,. \ \ \ \ \ (2)

First, let’s prove the (easy) LHS of (2). Suppose we have {S_1, S_2, \ldots, S_k \subseteq V} which are disjoint and non-empty and which satisfy {\phi(S_i) = \mathcal R(\mathbf{1}_{S_i}) \leq \rho} . Then certainly {W = \mathrm{span}(\mathbf{1}_{S_1}, \ldots, \mathbf{1}_{S_k})} is a {k} -dimensional subspace of {\ell^2(V)} . On the other hand, every {f \in W} satisfies {\mathcal R(f) \leq 2 \rho} because if {f = \alpha_1 \mathbf{1}_{S_1} + \cdots + \alpha_k \mathbf{1}_{S_k}} , then

\displaystyle  \sum_{u \sim v} (f(u)-f(v))^2 \leq 2 \sum_{i=1}^k \alpha_i^2 \sum_{u \sim v} |\mathbf{1}_{S_i}(u)-\mathbf{1}_{S_i}(v)|^2\,,

where we have used the fact that if {u \in S_i} and {v \in S_j} , then

\begin{array}{rcl} |\alpha_i \mathbf{1}_{S_i}(u) - \alpha_j \mathbf{1}_{S_j}(u)|^2 &\leq & 2(\alpha_i^2 + \alpha_j^2) \\ &=& 2\alpha_i^2 |\mathbf{1}_{S_i}(u) - \mathbf{1}_{S_i}(v)|^2 + 2\alpha_j^2 |\mathbf{1}_{S_j}(u)-\mathbf{1}_{S_j}(v)|^2\,.\end{array}

But now using (1), the subspace {W} witnesses the fact that {\lambda_k \leq 2\rho} .

To prove the more difficult RHS of (2), we will use the following discrete Cheeger inequality with boundary conditions.

Lemma 2 For any {f : V\rightarrow \mathbb R} , there is a subset {U \subseteq \{ v \in V : f(v) \neq 0\}} such that

\displaystyle  \phi(U) \leq \sqrt{2 \mathcal R(f)}\,.

Proof: Let {U_t = \{ v \in V : f(v)^2 \geq t \}} . Observe that for each {t > 0} , one has {U_t \subseteq \{ v \in V : f(v) \neq 0\}} . For {S \subseteq V} , let {E(S,\bar S)} denote the edges of {G} with exactly one endpoint in {S} . Then we have

\displaystyle  \begin{array}{rcl}  \int_0^{\infty} |E(U_t, \bar U_t)|\,dt &=& \sum_{\{u,v\} \in E} \left|f(u)^2 - f(v)^2\right| \\ &= & \sum_{\{u,v\} \in E} |f(u) + f(v)| |f(u)-f(v)| \\ &\leq & \sqrt{\sum_{\{u,v\} \in E} (|f(u)|+|f(v)|)^2} \sqrt{\sum_{\{u,v\} \in E} |f(u)-f(v)|^2} \\ &\leq & \sqrt{2 d \sum_{u \in V} f(u)^2}\sqrt{\sum_{\{u,v\} \in E} |f(u)-f(v)|^2}. \end{array}

On the other hand, {\int_0^{\infty} d|U_t|\,dt = d \sum_{u \in V} |f(u)|^2,} thus

\displaystyle  \int_0^{\infty} |E(U_t, \bar U_t)|\,dt \leq \sqrt{2 \mathcal R(f)} \int_0^{\infty} d|U_t|\,dt\,,

implying there exists a {t > 0} such that {\phi(U_t) = \frac{|E(U_t,\bar U_t)|}{d |U_t|} \leq \sqrt{2 \mathcal R(f)}} . \Box

In light of the preceding lemma, to prove the RHS of (2), it suffices to find {k} disjointly supported functions {\psi_1, \psi_2, \ldots, \psi_k : V \rightarrow \mathbb R} such that {\mathcal R(\psi_i) \leq (30)^2 k^6 \lambda_k} for each {i=1,2,\ldots,k} . Then Lemma 2 guarantees the existence of disjoint subsets of vertices satisfying our desired conclusion.

Toward this end, let {f_1, f_2, \ldots, f_k : V \rightarrow \mathbb R} denote {k} orthonormal functions satisfying {\mathcal L f_i = \lambda_i f_i} for each {i=1,2,\ldots,k} , i.e. consider the first {k} eigenfunctions of the Laplacian. Define the map {F : V \rightarrow \mathbb R^k} via

\displaystyle  F(v) = \left(f_1(v), f_2(v), \ldots, f_k(v)\right)\,.

We also put {\hat F(v) = F(v)/\|F(v)\|} . (Since {\lambda_1=0} , the function {f_1} takes value {1/\sqrt{n}} everywhere, hence {F} is never zero and this is well-defined.)

The next lemma shows that, in order to find disjointly supported functions, it suffices to find “separated sets.”

Lemma 3 Suppose that for some {\varepsilon > 0} and {0 < \delta \leq 1} , there exist {k} subsets {U_1, U_2, \ldots, U_k \subseteq V} satisfying the conditions:

  1. For every {i=1,2,\ldots,k} , we have {\sum_{v \in U_i} \|F(v)\|^2 \geq \varepsilon} , and
  2. For every {i \neq j} , if {u \in U_i} and {v \in U_j} , then

    \displaystyle  \|\hat F(u)-\hat F(v)\| \geq \delta

Then there are disjointly supported functions {\psi_1, \psi_2, \ldots, \psi_k : V \rightarrow \mathbb R} such that {\mathcal R(\psi_i) \leq 25k\lambda_k/(\varepsilon\delta^2)} .

Proof: For each {i=1,2,\ldots,k} , we define maps {\theta_i : V \rightarrow \mathbb R} by

\displaystyle  \theta_i(v) = \max\left(0, 1 - \frac{2}{\delta} \min_{u \in U_i} \|\hat F(u)-\hat F(v)\|\right)\,.

Observe that, by the triangle inequality, for {u,v \in V} , we have

\displaystyle  |\theta_i(u)-\theta_i(v)| \leq \frac{2}{\delta} \|\hat F(u)-\hat F(v)\|\,. \ \ \ \ \ (3)

Next, we define

\displaystyle  \psi_i(v) = \theta_i(v) \|F(v)\|\,.

Observe that since {\theta_i} is identically {1} on {U_i} , we have

\displaystyle  \sum_{v \in V} \psi_i(v)^2 \geq \sum_{v \in U_i} \|F(v)\|^2 \geq \varepsilon \ \ \ \ \ (4)

by condition (i).

Next, we argue that the functions {\{\theta_i\}} are disjointly supported. This immediately implies that the {\{\psi_i\}} are disjointly supported. If {u \in \mathrm{supp}(\theta_i) \cap \mathrm{supp}(\theta_j)} for some {i \neq j} , then there are points {v \in U_i} and {v' \in U_j} such that {\|\hat F(u)-\hat F(v)\| < \delta/2} and {\|\hat F(u)-\hat F(v')\| < \delta/2} . But then by the triangle inequality, {\|\hat F(v)-\hat F(v')\| < \delta} , violating condition (ii).

Finally, we bound {\mathcal R(\psi_i)} . For any {u,v \in V} and {i=1,2,\ldots,k} , we have

\displaystyle  |\psi_i(u)-\psi_i(v)| \leq \theta_i(u) \left|\vphantom{\bigoplus}\|F(u)\|-\|F(v)\|\right| + \|F(v)\| \cdot |\theta_i(u)-\theta_i(v)|\,. \ \ \ \ \ (5)

Now using (3),

\displaystyle  \|F(v)\| \cdot |\theta_i(u)-\theta_i(v)| \leq \frac{2}{\delta} \|F(v)\| \cdot \|\hat F(u)-\hat F(v)\| \leq \frac{4}{\delta} \|F(u)-F(v)\|\,, \ \ \ \ \ (6)

where we have used the fact that for any non-zero vectors {x,y \in \mathbb R^k} , we have

\displaystyle  \|x\| \left\|\frac{x}{\|x\|} - \frac{y}{\|y\|}\right\| = \left\|x - \frac{\|x\|}{\|y\|} y\right\| \leq \|x-y\| + \left\|y - \frac{\|x\|}{\|y\|} y\right\| \leq 2 \,\|x-y\|\,.

Using (6) and the fact that {\theta_i(u) \leq 1} in (5) yields

\displaystyle  |\psi_i(u)-\psi_i(v)| \leq \left(1+\frac{4}{\delta}\right) \|F(u)-F(v)\|\,. \ \ \ \ \ (7)

Finally, observe that

\displaystyle  \sum_{u \sim v} \|F(u)-F(v)\|^2 = \sum_{i=1}^k \sum_{u \sim v} |f_i(u)-f_i(v)|^2 = d (\lambda_1 + \cdots + \lambda_k) \leq dk\lambda_k\,.

Combining this with (7) and (4) shows that {\mathcal R(\psi_i) \leq \lambda_k \frac{k}{\varepsilon}(1+\frac{4}{\delta})^2 \leq 25k\lambda_k/(\varepsilon \delta^2).} \Box

We will first make the task of finding separated sets slightly easier.

Lemma 4 Suppose that for some {0 < \delta \leq 1} and {m \geq 1} , there are subsets {T_1, T_2, \ldots, T_m \subseteq V} which satisfy:

  1. {\displaystyle \sum_{i=1}^m \sum_{v \in T_i} \|F(v)\|^2 \geq k - \frac14} .
  2. For every {i \neq j} , if {u \in T_i} and {v \in T_j} , then { \|\hat F(u)-\hat F(v)\| \geq \delta }
  3. For every {i=1,2,\ldots, m} ,

    \displaystyle  \sum_{v \in T_i} \|F(v)\|^2 \leq 1 + \frac{1}{2k}\,.

Then there are {k} sets {U_1, U_2, \ldots, U_k \subseteq V} satisfying the assumption of Lemma 3 with {\varepsilon = \frac{1}{4}} .

Proof: We can form the desired sets {\{U_i\}} by taking disjoint unions of the sets {\{T_i\}} . Begin with the family {\{T_1, T_2, \ldots, T_m\}} and repeatedly replace two sets {T} and {T'} by their union if they each satisfy {\sum_{v \in T} \|F(v)\|^2 < \frac12} .

When we finish, we are left with a collection of sets each member of which satisfies {\sum_{v \in T} \|F(v)\|^2 \in [\frac12, 1+\frac{1}{2k}]} , and possibly one set for which {\sum_{v \in T} \|F(v)\|^2 < 1/2} . By (i), we must end with at least {k} sets which each satisfy {\sum_{v \in T} \|F(v)\|^2 \geq 1/4} . \Box

Our final lemma, which finishes the proof of Theorem 1, simply asserts that such sets exist. We will no longer need the fact that {F} comes from eigenfunctions.

Lemma 5 Suppose that {g_1, g_2, \ldots, g_k : V \rightarrow \mathbb R} are orthornormal in {\ell^2(V)} . Let

\displaystyle G(v) = (g_1(v), g_2(v), \ldots, g_k(v))

and {\hat G(v) = G(v)/\|G(v)\|} . Then there is an {m \geq 1} and subsets {T_1, T_2, \ldots, T_m \subseteq V} such that

  1. {\displaystyle\sum_{i=1}^m \sum_{v \in T_i} \|G(v)\|^2 \geq k - \frac14} .
  2. For every {i \neq j} , if {u \in T_i} and {v \in T_j} , then

    \displaystyle \|\hat G(u)-\hat G(v)\| \geq \frac{1}{2\sqrt{2} k^{3}}\,.

  3. For every {i = 1,2,\ldots,m} ,

    \displaystyle  \sum_{v \in T_i} \|G(v)\|^2 \leq 1 + \frac{1}{2k}\,.

Proof: Consider the {n \times k} matrix {A} which has columns {g_1, g_2, \ldots, g_k} . For any {x \in \mathbb R^k} , we have

\displaystyle  \sum_{v \in V} \langle x, G(v)\rangle^2 = \|Ax\|^2 = x^T A^T A x = x^T x = \|x\|^2\,, \ \ \ \ \ (8)

since the columns of {A} are orthornormal

For a subset {X \subseteq S^{k-1}} of the unit sphere in {\mathbb R^k} , we put {V(X) = \{ v \in V : \hat G(v) \in X \}} . Fix some {x \in X} and let {\mathsf{diam}(X)} denote the diameter of {X} , then by (8), we have

\displaystyle  1 = \sum_{v \in V(X)} \langle x, G(v)\rangle^2 = \sum_{v \in V(X)} \|G(v)\|^2 \left(1-\frac{\|\hat G(v)-x\|^2}{2}\right)^2 \geq \sum_{v \in V(X)} \|G(v)\|^2 \left(1-\frac{\mathrm{diam}(X)^2}{2}\right)^2\,.

We conclude that if {\mathrm{diam}(X) \leq 1/\sqrt{2k}} , then

\displaystyle  \sum_{v \in V(X)} \|G(v)\|^2 \leq 1 + \frac{1}{2k}\,. \ \ \ \ \ (9)

Now, let {\mathcal{P}} be a partition of {\mathbb R^k} into axis-parallel squares of side length {L = \frac{1}{k \sqrt{2}}} . For any such square {Q \in \mathcal P} , we let {\tilde Q \subseteq Q} denote the set of points which are at Euclidean distance at least {\frac{L}{4k^2}} from every side of {Q} . Observe that

\displaystyle  \mathrm{vol}(\tilde Q) \geq \left(1-\frac{1}{4k^2}\right)^k \mathrm{vol}(Q) \geq \left(1-\frac{1}{4k}\right) \mathrm{vol}(Q)\,. \ \ \ \ \ (10)

Consider now the collection of sets {\{V(\tilde Q) : Q \in \mathcal P\}} . Since {\mathrm{diam}(\tilde Q) \leq L \sqrt{k} = \frac{1}{\sqrt{2k}}} , (9) implies that {\sum_{v \in V(\tilde Q)} \|G(v)\|^2 \leq 1 + \frac{1}{2k}} . Furthermore, by construction, for any {u \in V(\tilde Q)} and {v \in V(\tilde Q')} with {Q \neq Q'} , we have

\displaystyle  \|\hat G(u)-\hat G(v)\| \geq 2 \frac{L}{4k^2} \geq \frac{1}{2\sqrt{2} k^{3}}\,.

Thus the collection of sets {\{V(\tilde Q) : Q \in \mathcal P\}} satisfy both conditions (ii) and (iii) of the lemma. We are left to verify (i).

Note that {\sum_{v \in V} \|G(v)\|^2 = \sum_{i=1}^k \sum_{v \in V} g_i(v)^2 = k} . If we choose a uniformly random axis-parallel translation {\mathcal P'} of the partition {\mathcal P} , then (10) implies

\displaystyle  \mathbb{E} \sum_{Q \in \mathcal P'} \sum_{v \in V(\tilde Q)} \|G(v)\|^2 \geq \left(1-\frac{1}{4k}\right) \sum_{v \in V(Q)} \|G(v)\|^2 \geq k - \frac14\,.

In particular, there exists some fixed partition that achieves this bound. For this partition {\mathcal P} , the sets {\{V(\tilde Q) : Q \in \mathcal P\}} satisfy all three conditions of the lemma, completing the proof.

Lecture 4: Conformal mappings, circle packings, and spectral geometry

In Lecture 2, we used spectral partitioning to rule out the existence of a strong parallel repetition theorem for unique games.  In practice, spectral methods are a very successful heuristic for graph partitioning, and in the present lecture we’ll see how to analyze these partitioning algorithms for some common families of graphs.

Balanced separators, eigenvalues, and Cheeger’s inequality

Lipton and Tarjan proved that every planar graph has a negligibly small set of nodes whose remval splits the graph into two roughly equal pieces.  More specifically, every n-node planar graph can be partitioned into three disjoint sets A,B,S such that there are no edges from A to B, the separator S has at most O(\sqrt{n}) nodes, and |A|,|B| \geq n/3.  This allows one to do all sorts of things, e.g. a simple divide-and-conquer algorithm gives a linear time (1+\epsilon)-approximation for the maximum independent set problem in such graphs, for any \epsilon > 0.

So there is a natural question of how well spectral methods do, for example, on planar graphs.  Spielman and Teng showed that for bounded-degree planar graphs, a simple recursive spectral algorithm recovers a partition V=A \cup B of the vertex set so that |E(A,B)| = O(\sqrt{n}).  In other words, for bounded-degree planar graphs, spectral methods recover the Lipton-Tarjan separator theorem!  This is proved by combining Cheeger’s inequality with their main theorem.

Theorem [Spielman-Teng]: Every n-node planar graph with maximum degree d_{\max} has \displaystyle \lambda_2(G) = O\left(\frac{d_{\max}}{n}\right), where \lambda_2(G) is the second eigenvalue of the combinatorial Laplacian on G.

Recall that we introduced the combinatorial Laplacian in Lecture 2.  If G=(V,E) is an arbitrary finite graph, in this lecture it will make more sense to think about the Laplacian \Delta as an operator on functions f : V \to \mathbb R given by

\displaystyle \Delta f(x) = \mathrm{deg}(x) f(x) - \sum_{y : xy \in E} f(y).

If we define the standard inner product \langle f,g\rangle = \sum_{x \in V} f(x)g(x), then one can easily check that for any such f, we have \langle f, \Delta f\rangle = \sum_{xy \in E} |f(x)-f(y)|^2.  In particular, this implies that \Delta is a positive semi-definite operator.  If we denote its eigenvalues by \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n, then it is also easy to check that \lambda_1 = 0, with corresponding eigenfunction f(x)=1 for every x\in V.

Thus by standard variational principles, we have

\displaystyle \lambda_2 = \min_{f \neq 0 : \sum_{x \in V} f(x)=0} \frac{\sum_{xy \in E} |f(x)-f(y)|^2}{\sum_{x \in V} f(x)^2}.

Let us also define the Cheeger constant h_G.  For an arbitrary subset S \subseteq V, let

\displaystyle h(S) = \frac{|E(S, \bar S)|}{\min(|S|,|\bar S|)},

note that this definition varies from the h we defined in Lecture 2, because we will be discussing eigenfunctions without boundary conditions.  Now one defines h_G = \min_{S \subseteq V} h(S).

Finally, we have the version of Cheeger’s inequality (proved by Alon and Milman in the discrete setting) for graphs without boundary.

Cheeger’s inequality: If G=(V,E) is any graph with maximum degree d_{\max}, then

\displaystyle \lambda_2(G) \geq \frac{h(G)^2}{2d_{\max}}.

This follows fairly easy from the Dirichlet version of Cheeger’s inequality presented in Lecture 2.  Here’s a sketch:  Let f : V \to \mathbb R satisfy \Delta f = \lambda_2 f, and suppose, without loss of generality, that V_+ = \{ x : f(x) > 0 \} has |V_+| \geq n/2.  Define f_+(x)=f(x) for f(x) > 0 and f_+(x)=0 otherwise.  Then f_+|_B = 0 for B = V \setminus V_+, so we can plug f_+ into the Dirichlet version of Cheeger’s inequality with boundary conditions on B.  For the full analysis, see this note which essentially follows this approach.  By examining the proof, note that one can find a subset S \subseteq V with h(S) \leq \sqrt{2 d_{\max} \lambda_2} by a simple “sweep” algorithm:  Arrange the vertices V = \{v_1, v_2, \ldots, v_n\} so that f(v_1) \leq f(v_2) \leq \cdots \leq f(v_n), and output the best of the n-1 cuts \{v_1, \ldots, v_i\}, \{v_{i+1}, \ldots, v_n\}.

So using the eigenvalue theorem of Spielman and Teng, along with Cheeger’s inequality, we can find a set S \subseteq V with h(S) \lesssim \sqrt{d_{\max}/n}.  While this cut has the right Cheeger constant, it is not necessarily balanced (i.e. \min(S, \bar S) could be very small).  But one can apply this algorithm recursively, perhaps continually cutting small chunks off of the graph until a balanced cut is collected.  Refer to the Spielman-Teng paper for details.  A great open question is how one might use spectral information about G to recover a balanced cut immediately, without the need for recursion.

Conformal mappings and circle packings

Now we focus on proving the bound \lambda_2(G) \lesssim d_{\max}/n for any planar graph G.  A natural analog is to look at what happens for the Laplace-Beltrami operator for a Riemannian metric on the 2-sphere.  In fact, Hersch considered this problem almost 40 years ago and proved that \lambda_2(M) \lesssim 1/\mathrm{vol}(M), for any such Riemannian manifold M.  His approach was to first use the uniformization theorem to get a conformal mapping from M onto S^2, and then try to pull-back the standard second eigenfunctions on S^2 \subseteq \mathbb R^3 (which are just the three coordinate projections).  Since the Dirichlet energy is conformally invariant in dimension 2, this almost works, except that the pulled-back map might not be orthogonal to the constant function.  To fix this, he has to post-process the initial conformal mapping with an appropriate Möbius transformation.

Unaware of Hersch’s work, Spielman and Teng derived eigenvalue bounds for planar graphs using the discrete analog of this approach:  Circle packings replace conformal mappings, and one still has to show the existence of an appropriate post-processing Möbius transformation.

Continue reading

Lecture 2: Spectral partitioning and near-optimal foams

In the last lecture, we reduced the problem of cheating in \mathcal G_m^{\otimes k} (the k-times repeated m-cycle game) to finding a small set of edges \mathcal E in (\mathbb Z_m^k)_\infty whose removal eliminates all topologically non-trivial cycles.  Such a set \mathcal E 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 k-dimensional torus \mathcal T^k = \mathbb R^k/\mathbb Z^k, which one can think of as \lbrack 0,1)^k with opposite sides identified.  Say that a nice set (e.g. a compact, C^\infty surface) \mathcal E \subseteq \mathcal T^k is a spine if it intersects every non-contractible loop in \mathcal T^k.  This is the continuous analog of a spine in (\mathbb Z_m^k)_\infty.  We will try to find such a spine \mathcal E with surface area, i.e. \mathrm{Vol}_{k-1}(\mathcal E), as small as possible.

Let’s consider some easy bounds.  First, it is clear that the set

\displaystyle \mathcal E = \left\{(x_1, \ldots, x_k) \in [0,1)^k : \exists i \in \{1,2,\ldots,k\}, x_i = 0\right\}

is a spine with \mathrm{Vol}_{k-1}(\mathcal E) = k.  (A moment’s thought shows that this is “equivalent” to the provers playing independent games in each coordinate of \mathcal G_m^{\otimes k}.)

To get a good lower bound, it helps to relate spines to foams which tile \mathbb R^k according to \mathbb Z^k, 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 \mathcal T^k, while the second yields a tiling of \mathbb R^k by bodies of volume 1.  It is easy to deduce the following claim.

Claim: A surface \mathcal E \subseteq \mathcal T^k 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 \mathbb Z^k.

By the isoperimetric inequality in \mathbb R^k, this immediately yields the bound

\displaystyle \mathrm{Vol}_{k-1}(\mathcal E) \geq \mathrm{Vol}_{k-1}(S^{k-1}) \approx \sqrt{k},

where S^{k-1} is the unit (k-1)-dimensional sphere.

So the the surface area of an optimal spine lies somewhere between k and \sqrt{k}.  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 \mathbb R^k by disjoint bodies of volume at most 1 so that the surface area/volume ratio grows like \sqrt{k}.  See Lemma 3.16 in this paper, which is based on Chekuri, et. al.  It’s just that these covers are not invariant under \mathbb Z^k 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 \mathsf{val}(\mathcal G_m^{\otimes k}) \approx 1 - \frac{k}{m}, which doesn’t rule out a strong parallel repetition theorem (\alpha^*=1 in the previous lecture).  If the “sphere bound” were tight, we would have \mathsf{val}(\mathcal G_m^{\otimes k}) \approx 1 - \frac{\sqrt{k}}{m}, which shows that \alpha^* \geq 2.   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 \mathsf{val}(\mathcal G_m^{\otimes k}) \geq 1 - C\frac{\sqrt{k}}{m} for some constant C > 0, 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 \mathcal E \subseteq \mathcal T^k with \mathrm{Vol}_{k-1}(\mathcal E) \approx \sqrt{k}.  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.

Continue reading

Parallel repetition, unique games, and spectral partitioning

Yesterday, Anup Rao pointed me to these two remarkably beautiful papers, which made my morning coffee taste a little better, and the Boston sun feel a bit warmer. I thought I’d pass on the good vibes.

Economical toric spines via Cheeger’s inequality

and

Rounding parallel repetitions of unique games

both of which have their genesis in a recent paper of Ran Raz.

I will actually post detailed notes on these developments in the coming months, as part of my upcoming course on Analytical and geometric methods in the theory of computation (and this link will also work at some point).

[Two more comments worth mentioning:  First, the rounding paper above essentially matches the CMM algorithm even for non-repeated unique games, with a (perhaps) more natural algorithm.  Secondly, as part of RANDOM-APPROX’08, Anup is giving a survey talk on these topics tomorrow morning (Wed, 8/27) at 9am in the Stata center.]