Abstract
The Unique Games Conjecture (UGC) is a central open question in computational complexity and algorithms. In short, the UGC stipulates that almost satisfiable instances of Unique Games, a certain 2-variable constraint satisfaction problem (CSP), are NP-hard to distinguish from highly unsatisfiable instances. The UGC is known to imply a vast number of hardness-of-approximation results in combinatorial optimization.
In this talk I will discuss our results that give algorithms for Unique Games (UG) on a large class of restricted instances: certifiable small-set expanders and graphs with certifiable global hypercontractivity. Our first algorithm solves UG instances whenever low-degree sum-of-squares (SoS) proofs certify good bounds on the small-set-expansion of the underlying constraint graph. A more complicated version of our algorithm succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is “characterized” by a low-degree SoS proof, a property we call certified global hypercontractivity. The latter algorithm gives new insights into the breakthrough 2-2 Games hardness result, in particular, gives us some evidence as to what hard instances of UG look like.