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 \(\e\) fraction of the edges such that every component has at most \(n^\beta\) eigenvalues larger than \(\lambda\), where \(\beta=\beta(\e,\lambda)\) goes to \(0\) for any fixed \(\lambda\) as long as \(\e\) 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\)).
approximation algorithms, small-set expansion, Unique Games Conjecture, constraint satisfaction problems, eigenvalues.