Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansion
We show subexponential-time algorithms for d-to-1 two-prover games, a broad class of constraint satisfaction problems. The algorithm achieves a better approximation guarantee than the basic semidefinite relaxation. The algorithm also has consequences for Khot's d-to-1 Conjectures. We also give a related subexponential-time algorithm for certifying that small sets in a graph have almost perfect expansion.
Our algorithms follow the basic approach of the subexponential-time algorithms for Unique Games and Small-Set Expansion (Arora, Barak, Steurer, FOCS 2010), but differ in the implementation of the individual steps.
A key ingredient is a graph decomposition algorithm that finds for every graph, a subgraph with at least an fraction of the edges such that every component has at most eigenvalues larger than , where goes to for any fixed as long as goes to . To the best of our knowledge this spectral graph partitioning result is the first that applies to the whole range of eigenvalues (as opposed to just eigenvalues close to ).
- approximation algorithms
- small-set expansion
- Unique Games Conjecture
- constraint satisfaction problems