Notes of David Steurer’s lecture nr 3


Subexponential algorithm for Unique Games


1. Result


  • Input: {n} variables, an integer {k}, constraints of the form {x_i -x_j =c} mod {k}.
  • Output: an assignment.
  • Objective: maximize fraction of satisfied constraints.

UGC states that for every {\epsilon}, {\exists k} such that {(1-\epsilon,\epsilon)}-approximation is NP-hard. Although not explicitly specified, {k} should not be too large ({k=O(\log n)}).

Let {UG(c,\epsilon)} be the following promise problem. Given an instance of Unique Games with value {\geq 1-\epsilon^c}, find an assignment of value {\geq 1-\epsilon}. We (Arora-Barak-Steurer, [ABS] ) prove

Theorem 1 There exists a constant {c} such that for all {k}, {\textrm{UG}(c,\epsilon)\in} TIME{(2^{kn^{O(\epsilon^{1/3})}})}.


Remark 1

  • This shows that MAX BIJECTION is much easier than MAX PROJECTION, for which no subexponential algorithm is expected to exist.
  • This shows that reduction from 3SAT to UGC{(\epsilon)} has running time {n^{\Omega(1/\epsilon^{1/3})}} unless 3SAT has a subexponential algorithm.
  • This implies that UGC{(\epsilon)} for {\epsilon=o(1)} is false unless 3SAT has a subexponential algorithm.


2. Outline of proof


  1. Prove the theorem if constraint graph is a quasi-hypercube.
  2. Every graph can be approximated by a disjoint union of such quasi-hypercubes (up to a small fraction of edges).

Both steps rely on graph expansion. Let us set up notations. For a {d}-regular graph, and a subset {S} of vertices,

\displaystyle  \begin{array}{rcl}  \Phi(S)=\frac{E(S,\bar{S})}{d|S|}. \end{array}

Let {G} denote the normalized adjacency matrix, {x=1_{S}/|S|}. Then

\displaystyle  \begin{array}{rcl}  1-\Phi(S)=x^{\top}Gx. \end{array}

Today, I explain step 2. Tomorrow’s lecture will contain allusions to step 1.


3. Decomposition into quasi-hypercubes


3.1. Quasi-hypercubes


The hypercube {\{ 0,1 \}^d} has eigenvalues {\lambda_i} equal to {d}, {d-2},… with multiplicities given by binomial coefficients. In particular, given {\beta<1}, for {m=\begin{pmatrix} d \\ \beta d \end{pmatrix}}, {\lambda_m \sim 1-\beta}.

Definition 2 Fix {\beta=O(\epsilon^{1/3})}, {m=n^{O(\beta)}}. Say a graph is a quasi-hypercube if {|\lambda_1 -\lambda_m|>\epsilon} and {\lambda_m <1-\epsilon}.


Example 1 Expanders are quasi-hypercubes.


Theorem 3 By removing at most 1% of edges, every regular {n}-vertex graph can be split into a disjoint union of quasi-hypercubes.


Warm-up: if {\epsilon=1/O(\log n)^3} (which makes {m=2}), this follows from Cheeger’s inequality,

\displaystyle  \begin{array}{rcl}  \lambda_2 \geq 1-\epsilon \quad\Rightarrow \quad \exists S \textrm{ such that }|S|\leq\frac{1}{2}|V|,~ \Phi(S)\leq o(\sqrt{\epsilon}). \end{array}

Recursively, apply Cheeger’s inequality to each connected component of current graph {G'}, cut it in two parts, charge {\Phi(S)} to vertices in the smaller part {S}. Since the size of {S} gets halved at each step, no vertex can be charged more than {\log n} times. Cheeger’s inequality implies that the total charge is {\leq O(\sqrt{\epsilon})\log n}. This is larger than the average number of removed edges per vertex. So the total number of removed edges is {<O(n\sqrt{\epsilon})\log n}, and the fraction of removed edges is {<O(\sqrt{\epsilon})\log n=o(\epsilon)}.

This does not suffice, since we do not want {\epsilon} to depend on {n}.


3.2. Higher order Cheeger bound


Theorem 4

\displaystyle  \begin{array}{rcl}  \lambda_m \geq 1-\epsilon \quad\Rightarrow \quad \exists S \textrm{ such that }|S|\leq n^{-\beta}|V|,~ \Phi(S)\leq o(\sqrt{\frac{\epsilon}{\beta}}). \end{array}

Assuming this, we finish the proof of the decomposition theorem. Use same decomposition and charging pattern. This time, the size of {S} is divided by {n^{\beta}} at each step, so no vertex can be charged more than {1/\beta} times. The higher order Cheeger bound implies that the total charge is {\leq O(\sqrt{\frac{\epsilon}{\beta}})\frac{1}{\beta}}, so is the fraction of removed edges.


3.3. Proof of higher order Cheeger bound


Idea: There is a vertex such that the random walk from it is stuck in a neighborhood for a long time. Formally,

Claim: Let {t=\frac{\beta}{\epsilon}\log n}. There exists a vertex {i} such that

\displaystyle  \begin{array}{rcl}  \|G^{t}1_{i}\|_{2}^{2}\geq \frac{n^{\beta}}{n}. \end{array}

Proof: Sum up conditional probabilities. Since {1_i} constitute an orthonormal basis of {\ell^2 (V)},

\displaystyle  \begin{array}{rcl}  \sum_{i}\|G^{t}1_{i}\|_{2}^{2}&=&\mathrm{Trace}(G^{2t})\\ &=&\sum_{j}\lambda_{j}^{2t}\\ &\geq&n^{O(\beta)}(1-\epsilon)^{2t}\\ &=& n^{\beta}. \end{array}


Assume claim. There is {s<t} such that {\|G^{s+1}1_{i}\|_{2}^{2}\geq (1-\frac{\beta}{\epsilon})\|G^{s}1_{i}\|_{2}^{2}}, i.e., for {x=G^{s}1_{i}}, {x^{\top}Gx\geq (1-\frac{\beta}{\epsilon})\|x\|^2}. A local version of Cheeger’s inequality gives that if there is a vector {x} with {\|x\|^{2}>1/W} and {\|G^2 x\|^2 \geq (1-\eta)\|x\|^2}, then there is a subset {S} with {|S|<2W} and {\Phi(S)\leq O(\sqrt{\eta})}. For {x=G^{s}1_{i}}, {\|x\|^2 \geq \|G^{t}1_{i}\|^2 \geq n^{\beta-1}}, so take {W=n^{1-\beta}}, {\eta=\frac{\beta}{\epsilon}}, and get higher order Cheeger inequality.


4. Why one may decompose


Assume we have an algorithm which, when run on a decomposed graph whose {OPT} is {\geq 1-\epsilon^c}, outputs in subexponential time an assignment which satisfies a fraction {\geq 1-\epsilon} of constraints. Let {I=(G,\{\pi_e\})} be a unique game instance such that {OPT(I)\geq 1-\epsilon}. Decompose {G}. Assume that a fraction {<\epsilon^c} of the edges of {G} have been removed. Get a new instance {I'} of unique games. Then {OPT(I')\geq 1-2\epsilon^c}. Run the algorithm. In subexponential time, it outputs an assignment which satisfies a fraction {\geq 1-2^{1/c}\epsilon} of constraints. This assignment probably fails on removed edges, but nevertheless has value {\geq (1-\epsilon^c)(1-2^{1/c}\epsilon)\sim 1-O(\epsilon)}.




[ABS] Arora, Sanjeev; Barak, Boaz; Steurer, David; Subexponential Algorithms for Unique Games and Related Problems. FOCS 2010.



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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s