Seminars
View all Seminars | Download ICal for this eventUnique Games and Expansion
Series: Bangalore Theory Seminars
Speaker: Mitali Bafna Carnegie Mellon University (CMU)
Date/Time: Jul 06 21:00:00
Location: Microsoft Teams - Online Talk (See Teams link below)
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.
Microsoft Teams link:
Link
We are grateful to the Kirani family for generously supporting the theory seminar series
Hosts: Rameesh Paul, Rachana Gusain, Rahul Madhavan, KVN Sreenivas