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 . Specificly, if when and .
Theorem 1 For all , there is a -approximation for Unique Games in subsexponential time.
1.1. Subspace enumeration
Given a unique game instance, construct the label-extended graph : vertices are and connect to if is an edge and .
Given an assignment that satisfies fraction of constraints, its graph has expansion in the label-extended graph. This is the only property of unique games instances that we shall use.
Let denote the linear span of eigenfunctions of with eigenvalue .
Claim: If a set has expansion ,
1.2. The algorithm
The algorithm (due to Kolla and Tulsiani 2007 when )
- discretizes ;
- finds with close to , which is close to according to Claim;
- decodes a set close to and an assignment close to .
This takes time exponential in the dimension of .
We can assume that . Since , this implies that .
2. Small Set Expansion
We just saw that sets of volume fraction having small expansion play a role in unique games with 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.
Definition 2 Given , the SSE problem has
- Input: a graph .
- Output: a set of vertices with volume fraction .
- Objective: minimize edge expansion.
Definition 3 The SSE hypothesis is the following question. For all , such that -approximating SSE 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 -CUT, MAX CUT on SSE graphs.
For instance, it is SSE-hard to -approximate SPARSEST CUT.
Our reductions cannot be local gadget reductions, since these preserve expansion.
2.2. Reduction from SSE to UG
Given a graph and , we construct a unique game instance with label size . It has two provers and and one verifier. The verifier picks a set of disjoint random edges in and gives the set of origins to and the set of ends to . Each picks a vertex , , then they communicate and check wether .
Completeness: Given of volume fraction and . Here is a strategy for : pick , refuse to answer if .
Soundness: We must construct a set of small expansion. Let , be the strategies of players. Given sets and of vertices, define
Since , typically the volume fraction is right. I claim that
This implies that randomly chosen , 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.