## 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 ${, and the fraction of removed edges is ${.

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}$

$\Box$

Assume claim. There is ${s 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)}$.

References

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