Unique Games Conjecture: (Khot’02) For every \(\epsilon\), \(UG(\epsilon)\) is NP hard.

For eq’s involving three variables, distinguishing \(1-o(1)\) and \(1/k+o(1)\) is exponentially NP hard (Hastad, Moshkovitz-Raz)

Thm: (Arora-B-S) Can solve \(UG(\epsilon)\) in \(\exp(n^{O(\epsilon^{1/3})})\) time.

Define \(G\) on \(nk\) vertices where \((i,a) \sim (j,b)\) iff \(a+b = c_{i,j}\).

Recall \(f_G(x) = \tfrac{1}{E_G} \sum_{i\sim j} (x_i-x_j)^2\)

Identify \(x\in {\mathbb{Z}}_k\) with \(\hat{x}\) in \({\{0,1\}}^{nk}\) (\(\hat{x}_{i,a}=1\) iff \(x_i=a\))

Claim: If \(x\) satisfies \((1-\epsilon)m\) equations, then \(f_G(\hat{x}) \leq \epsilon \mu(\hat{x})\).

(Def’n: \(\mu(x):={\| x \|}^2/n\) (\(=|x|/n\) if \(x\in{\{0,1\}}^n\)) )

Small Set Expansion Hypothesis: (Raghavendra-S’12) For every \(\epsilon\), \(SSE(\epsilon)\) is NP hard.

Saw: Map \({\mathcal{E}}\leadsto G\) s.t. \(\max_{x\in{\mathbb{Z}}_k} {\mathcal{E}}(x) \geq 1-\epsilon \Rightarrow \varphi_G(1/k) \leq \epsilon\).

Theorem: (Raghavendra-S’12) SSEH implies UGC

Thm: (Arora-B-S) Can solve \(SSE(\epsilon)\) in \(\exp(n^{O(\epsilon)})\) time.

Given graph \(G\), define \(0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n\) be eigenvalues of \(I-(1/d)A_G\).

Cheeger’s Ineq: If \(\varphi_G(1/2) \geq \epsilon\) then \(\lambda_2 \geq \Omega(\epsilon^2)\).

Cor: For \(m=n^{O(\sqrt{\epsilon})}\), if \(\lambda_m \geq 1000\epsilon\) then \(\varphi_G(\lambda) \leq 0.1\).

Proof: For every \(x\), if \(\tilde{x}=x/{\| x \|} = \sum \alpha_i v_i\) then \(f_G(x)/\mu(x)=\tfrac{1}{d{\| x \|}^2}\sum_{i \sim j} (x_i-x_j)^2 = \sum_i \alpha_i^2 \lambda_i\).

So if \(f_G(x)/|x| \leq \epsilon\) and \(\lambda_{m} \geq 100\epsilon\) then \(\sum_{i\gt m} \alpha_i^2 \lt 0.001\).

Projection of \(x\) to \(Span\{ v_1,\ldots, v_m \}\) has \(0.99{\| x \|}\) norm.

\(\Rightarrow\) \(\exp(O(m))\) time algorithm to find it. ∎

Cheeger’s Inequality: If \(f_G(x)\leq \epsilon {\| x \|}_2^2\) then there is threshold \(S\) cut of \(x\) s.t. \(f_G(1_S) \leq O(\sqrt{\epsilon} \mu(S)\).

Cor: If \(\mu(\{ i : x_i \gt 0 \}) \leq \delta\) then set measure \(\leq \delta\).

\(x'_i = x_i\) if \(|x_i| \gt {\| x \|}_2/(2\sqrt{n})\), \(x'_i=0\) otherwise.

\({\| x' \|}^2 \geq {\| x \|}^2/2\) and \(f_G(x') \leq f_G(x) \leq \epsilon 2{\| x' \|}^2\)

But \(|\{ i : x'_i \neq 0 \}| \leq 2\sqrt{\delta} n\)

∎

Reduces structure theorem to following:

Proof: Let \(\Pi\) be projector to \(v_1,\ldots,v_{n^\beta}\). \(Tr(\Pi) = n^\beta\). Assume \(e_1^\top \Pi e_1 \geq n^{\beta-1}\)

\(w\in \Pi \color{red}{\Rightarrow} w^\top A_G w \geq (1-\epsilon){\| w \|}^2\)

\(v_t\) := dist of \(t\) step “lazy random walk” from \(1\). (\(v_t = \left(\tfrac{1}{2}I+\tfrac{1}{2}A_G\right)^t e_i\))

\({\| v_t \|}_2^2 \geq n^{\beta-1}(1-\epsilon)^t\), \({\| v_t \|}_1=1\)

Find \(t \leq 0.1\beta \log n/\epsilon\) s.t. \({\| v_t \|}/{\| v_{t-1} \|} \geq 1- O(\epsilon/\beta)\) ∎

Thm: (B-Raghavendra-S) Do so via \(n^{O(\epsilon)}\) degree SOS.

Proof: By structure thm, every pseudo-dist (over unit vectors) will have \({\tilde{\mathbb{E}}}{\| \Pi x \|}^2 \geq 0.99\).

use

Fix vector in subspace thm: If \(\mu\) is degree \(O(d)\) over unit vecs dimension \(d\) subspace \(V\) and \(w\) random Gaussian in \(V\), then \({\tilde{\mathbb{E}}}_{v\sim \mu} {\langle w,v \rangle}^{O(d)} vv^\top\) has \(\sim\) rank one.

Proof: Apply Cheeger recursively.

SSE partitioning lemma: (Arora-B-S) By removing \(0.01\) fraction of edges, can decompose every graph into disjoint collection of graphs with \(\lambda_{n^{O(\epsilon^{1/3})}} \gt \Omega(\epsilon)\)

Proof: Apply structure theorem recursively.

Corollary: Enough to solve \(UG(\epsilon)\) in \(\exp(O(m))\) time for graphs where \(\lambda_m \geq 1000\epsilon\).

Can be done via “fix vector in subspace thm”

Example: Noisy cube: \(V_G = {\{0,1\}}^{\log n}\), \(x \sim y\) if \(\Delta(x,y) \leq 0.01\log n\). \(\log n\) eigenvalues of valuse \(0.01\). If \(\mu(S) = 2^{-t}\) then \(f_G(x) \geq (1-0.99^t)\mu(x)\).

Short code graph: (B-Gopalan-Hastad-Meka-Raghavendra-S’11) \(V_G = \{ p:{\mathbb{F}}_2^\ell\to{\mathbb{F}}\;|\; \deg(p)\leq d \}\). \(n=2^{\ell^d}\). \(p \sim q\) iff \(p-q=\alpha(x)^d\). \(\ell = \exp((\log n)^{1/d})\) eigenvalues of value \(1-2^{-d}\) s.t. if \(\delta=o(1)\) then \(\varphi_G(\delta)\geq 1-2^{-2^d}-o(1)\).

SOS Strikes back: Degree \(16\) SOS can certify SSE of the short code! (B-Brandao-Harrow-Kelner-Steurer-Zhou’12)

From quantum with love: Good enough algorithms for identifying entanglement could refute small set expansion, speed up ABS. (B-Brandao-Harrow-Kelner-Steurer-Zhou’12, B-Kothari-S’17)

UGC: \(\xi(UG,1-\epsilon,\epsilon)\gt0\)

Raghavendra’s Thm: UGC implies for every predicate \(P\), \(\xi(P,s,c)=0\) iff degree \(2\) SOS (+ lin constraints) solves \(CSP(P)_{c+o(1) \text{ vs } s-o(1)}\).

Conjecture: \(\xi(P,s,c) \sim \log_n deg_SOS(CSP(P))_{c \text{ vs } s}\)