# Playing Unique Games on Certified Small-Set Expanders

with Mitali Bafna, Boaz Barak, Pravesh Kothari, Tselil Schramm. **STOC 2021.**

## abstract

We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint graph via a hypercontractive inequality. Our algorithm is in fact more versatile, and succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is (informally speaking) characterized by a low-degree sum-of-squares proof. Our results are obtained by rounding *low-entropy* solutions—measured via a new global potential function—to sum-of-squares (SoS) semidefinite programs. This technique adds to the (currently short) list of general tools for analyzing SoS relaxations for *worst-case* optimization problems.

As corollaries, we obtain the first polynomial-time algorithms for solving any UG instance where the constraint graph is either the *noisy hypercube*, the *short code* or the *Johnson* graph. The prior best algorithm for such instances was the eigenvalue enumeration algorithm of Arora, Barak, and Steurer (2010) which requires quasi-polynomial time for the noisy hypercube and nearly-exponential time for the short code and Johnson graphs. All of our results achieve an approximation of $1-\epsilon$ vs $\delta$ for UG instances, where $\epsilon>0$ and $\delta > 0$ depend on the expansion parameters of the graph but are independent of the alphabet size.

## keywords

- Unique Games Conjecture
- small-set expansion
- sum-of-squares