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

Proof:

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

$\Box$

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}). 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.

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

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.

References