Notes of David Steurer’s lecture nr 4

Today, I briefly explain the subexponential algorithm for Unique Games on quasi-hypercubes, and then move on to Small Set Expansion.


1. Unique games on quasi-hypercubes


We prove the following theorem for graphs which have not too many eigenvalues close to {1}. Specificly, if {\lambda_m <1-\epsilon} when {m=O(n^{\beta})} and {\beta=O(\epsilon^{1/3})}.

Theorem 1 For all {\epsilon>0}, there is a {(1-\epsilon,\epsilon)}-approximation for Unique Games in subsexponential time.


1.1. Subspace enumeration


Given a unique game instance, construct the label-extended graph {\hat{G}}: vertices are {V\times[k]} and connect {(i,a)} to {(j,b)} if {ij} is an edge and {\pi_{ij}(a)=b}.

Given an assignment that satisfies fraction {1-\epsilon} of constraints, its graph {S=\{(i,a)\,;\, x_i =a\}} has expansion {\Phi(S)=\epsilon} in the label-extended graph. This is the only property of unique games instances that we shall use.

Let {\mathcal{U}} denote the linear span of eigenfunctions of {\hat{G}} with eigenvalue {>1-\epsilon}.

Claim: If a set {S\subset \hat{G}} has expansion {\Phi(S)=\epsilon},

\displaystyle  \begin{array}{rcl}  \|P_{\mathcal{U}}1_S\|^2 \geq 0.99 \|1_S\|^2. \end{array}


\displaystyle  \begin{array}{rcl}  1_S^{\top}G1_S \leq \|P_{\mathcal{U}}1_S\|^2 +(1-\epsilon)(1-\|P_{\mathcal{U}}1_S\|^2 ). \end{array}



1.2. The algorithm


The algorithm (due to Kolla and Tulsiani 2007 when {\lambda_2 <1-\epsilon})

  1. discretizes {\mathcal{U}};
  2. finds {x\in\mathcal{U}} with {x} close to {P_{\mathcal{U}}1_S}, which is close to {1_S} according to Claim;
  3. decodes a set {S'} close to {S} and an assignment {x'} close to {x}.

This takes time exponential in the dimension of {\mathcal{U}}.


1.3. Analysis


We can assume that {\mathrm{Trace}(G^{2t})<n^{\beta}}. Since {\mathrm{Trace}(\hat{G}^{2t})\leq k\mathrm{Trace}(G^{2t})}, this implies that {\hat{\lambda}_{km}<1-\epsilon}.


2. Small Set Expansion


We just saw that sets of volume fraction {1/k} having small expansion play a role in unique games with {k} labels. Assignments with high value give rise to such sets. We do not know if, conversely, sets with small expansion have to be close to assignements. So this does not lead to a reduction to Unique Games. We shall see that the reduction works in the opposite direction.


2.1. Results


Definition 2 Given {\delta>0}, the SSE{(\delta)} problem has

  • Input: a graph {G}.
  • Output: a set {S} of vertices with volume fraction {\delta}.
  • Objective: minimize edge expansion.


Definition 3 The SSE hypothesis is the following question. For all {\epsilon>0}, {\exists \delta=\delta(\epsilon)} such that {(1-\epsilon,\epsilon)}-approximating SSE{(\delta)} is NP-hard.


With Prasad Raghavendra, I prove

Theorem 4 SSE hypothesis implies UGC. UGC + an extra assumption on the label-extended graph implies SSE hypothesis.


With Prasad Raghavendra and Madhur Tulsiani, I prove

Theorem 5 SSE hypothesis implies hardness of approximation for SPARSEST CUT, MIN {k}-CUT, MAX CUT on SSE graphs.

For instance, it is SSE-hard to {(\sqrt{\epsilon}/100,\epsilon)}-approximate SPARSEST CUT.

Our reductions cannot be local gadget reductions, since these preserve expansion.


2.2. Reduction from SSE to UG


Given a graph {G} and {\delta>0}, we construct a unique game instance with label size {R=1/\delta}. It has two provers {P1} and {P2} and one verifier. The verifier picks a set {M} of {R} disjoint random edges in {G} and gives the set {A} of origins to {P1} and the set {B} of ends to {P2}. Each picks a vertex {a\in A}, {b\in B}, then they communicate and check wether {ab\in M}.


2.3. Analysis


Completeness: Given {S\in G} of volume fraction {\delta} and {\Phi(S)<\epsilon}. Here is a strategy for {P1}: pick {a\in A\cap S}, refuse to answer if {A\cap S=\emptyset}.

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb P}(M\cap E(S,\bar{S})=\emptyset)&\geq& (1-\epsilon\delta)^R \geq 1-\epsilon.\\ \mathop{\mathbb P}(|A\cap S|=1)=R\delta(1-\delta)^{R-1}\sim e^{-1}. \end{array}

Soundness: We must construct a set of small expansion. Let {f}, {g} be the strategies of players. Given sets {A'} and {B'} of {R-1} vertices, define

\displaystyle  \begin{array}{rcl}  S_{A'} &=&\{a\,;\, f(A'\cup\{a\})=a\},\\ T_{B'} &=&\{b\,;\, g(B'\cup\{b\})=b\}. \end{array}

Since {\mathop{\mathbb E}_{A'}(|S_{A'}|/|V|)=1/R}, typically the volume fraction is right. I claim that

\displaystyle  \begin{array}{rcl}  \mathop{\mathbb E}_{M'\in E^{R-1}}(|E(S_{A'},T_{B'})|)>\frac{\epsilon}{R}. \end{array}

This implies that randomly chosen {S_{A'}}, {T_{B'}} have a substantial number of edges between them, so their union has few outgoing edges, i.e. not too large expansion.

In reality, it is necessary to introduce some noise in this construction.






About metric2011

metric2011 is a program of Centre Emile Borel, an activity of Institut Henri Poincaré, 11 rue Pierre et Marie Curie, 75005 Paris, France. See
This entry was posted in Workshop lecture and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s