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

PDF

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