On Unique Games and High Dimensional Expansion

On Unique Games and High Dimensional Expansion

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 the first part of the talk I will discuss my recent works 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 us new insights into the source of hardness in the breakthrough result that proved the 2-2 games conjecture.
In the second part of the talk, I will discuss our work that develops a new theory of global hypercontractivity on high dimensional expanders (HDX), an important class of graphs that generalize the well-studied Johnson graphs. Combined with the algorithmic framework discussed above our results imply algorithms for UG on HDX. Our algorithmic techniques add to the (currently short) list of general tools for analyzing SoS relaxations for worst-case optimization problems and connect the UGC to the small-set expansion hypothesis and the theory of high-dimensional expansion.
Bio: Mitali ia a postdoc at CMU hosted by Prof. Aayush Jain and Prof. Pravesh Kothari. Before this, she was a graduate student in theoretical computer science at Harvard University where she was advised by Prof. Madhu Sudan. She did my undergrad in computer science from IIT Madras.Her research is focussed on complexity theory and algorithms, specifically the complexity of combinatorial optimization problems, sum of squares algorithms and high dimensional expanders.