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


unpublished manuscript


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βn^\beta eigenvalues larger than λ\lambda, where β=β(ε,λ)\beta=\beta(\varepsilon,\lambda) goes to 00 for any fixed λ\lambda as long as ε\varepsilon goes to 00. 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 11).


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