Subexponential algorithms for d-to-1 two-prover games and for certifying almost perfect expansion

unpublished manuscript

abstract

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 $\varepsilon$ fraction of the edges such that every component has at most $n^\beta$ eigenvalues larger than $\lambda$ , where $\beta=\beta(\varepsilon,\lambda)$ goes to $0$ for any fixed $\lambda$ as long as $\varepsilon$ goes to $0$ . 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 $1$ ).

keywords

approximation algorithms
small-set expansion
Unique Games Conjecture
constraint satisfaction problems
eigenvalues