Subexponential algorithm for Unique Games
- Input: variables, an integer , constraints of the form mod .
- Output: an assignment.
- Objective: maximize fraction of satisfied constraints.
UGC states that for every , such that -approximation is NP-hard. Although not explicitly specified, should not be too large ().
Let be the following promise problem. Given an instance of Unique Games with value , find an assignment of value . We (Arora-Barak-Steurer, [ABS] ) prove
Theorem 1 There exists a constant such that for all , TIME.
- 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 has running time unless 3SAT has a subexponential algorithm.
- This implies that UGC for is false unless 3SAT has a subexponential algorithm.
2. Outline of proof
- Prove the theorem if constraint graph is a quasi-hypercube.
- 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 -regular graph, and a subset of vertices,
Let denote the normalized adjacency matrix, . Then
Today, I explain step 2. Tomorrow’s lecture will contain allusions to step 1.
3. Decomposition into quasi-hypercubes
The hypercube has eigenvalues equal to , ,… with multiplicities given by binomial coefficients. In particular, given , for , .
Definition 2 Fix , . Say a graph is a quasi-hypercube if and .
Example 1 Expanders are quasi-hypercubes.
Theorem 3 By removing at most 1% of edges, every regular -vertex graph can be split into a disjoint union of quasi-hypercubes.
Warm-up: if (which makes ), this follows from Cheeger’s inequality,
Recursively, apply Cheeger’s inequality to each connected component of current graph , cut it in two parts, charge to vertices in the smaller part . Since the size of gets halved at each step, no vertex can be charged more than times. Cheeger’s inequality implies that the total charge is . 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 to depend on .
3.2. Higher order Cheeger bound
Assuming this, we finish the proof of the decomposition theorem. Use same decomposition and charging pattern. This time, the size of is divided by at each step, so no vertex can be charged more than times. The higher order Cheeger bound implies that the total charge is , 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 . There exists a vertex such that
Proof: Sum up conditional probabilities. Since constitute an orthonormal basis of ,
Assume claim. There is such that , i.e., for , . A local version of Cheeger’s inequality gives that if there is a vector with and , then there is a subset with and . For , , so take , , and get higher order Cheeger inequality.
4. Why one may decompose
Assume we have an algorithm which, when run on a decomposed graph whose is , outputs in subexponential time an assignment which satisfies a fraction of constraints. Let be a unique game instance such that . Decompose . Assume that a fraction of the edges of have been removed. Get a new instance of unique games. Then . Run the algorithm. In subexponential time, it outputs an assignment which satisfies a fraction of constraints. This assignment probably fails on removed edges, but nevertheless has value .