On High Dimensional Expansion and The Complexity of Unique Games

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 thesis we give algorithms for unique games (UG) on a large class of restricted instances: \emph{certifiable small-set expanders} and graphs with \emph{certifiable global hypercontractivity}. Our first algorithm solves unique games instances whenever low-degree sum-of-squares (SoS) proofs certify good bounds on the small-set-expansion of the underlying constraint graph, giving us polynomial time algorithms for UG on the noisy-hypercube and short-code graphs. 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, implying UG algorithms for the well-studied Johnson graphs.

We develop a new theory of global hypercontractivity on high dimensional expanders (HDX), an important class of expanding complexes that generalize the Johnson graphs. Our results generalize the structure theorems for Johnson graphs leading to a new understanding of the structure of Boolean functions on HDX and a characterization of non-expanding sets in such graphs. Using the algorithmic framework discussed above combined with these hypercontractive inequalities, we get unique games algorithms on HDX with approximation factor and runtime depending on a combinatorial quantity we call the stripped threshold rank of the graph.

Our algorithmic techniques add to the (currently short) list of general tools for analyzing SoS relaxations for worst-case optimization problems, connect the UGC to the small-set expansion hypothesis and the study of high-dimensional expansion, and shed some light on the source of hardness in the instances for 2-2 games obtained in recent breakthrough work of~~\cite{KhotMS18} (building on \cite{KhotMS17,DinurKKMS18,BarakKS19,KMMS}) proving the NP-hardness of 2-2 games.