Mitali Bafna: Playing Unique Games on Certifiable Small-Set Expanders and High-Dimensional Expanders

Passcode: 319645

The Unique Games Conjecture (UGC) is a central open question in computational complexity and algorithms. In short, the UGC stipulates that distinguishing between almost satisfiable and highly unsatisfiable instances of a certain 2-variable constraint satisfaction problem (CSP) called Unique Games is NP-hard. We build algorithms for UG on a large class of restricted instances including certified small-set expanders, Johnson graphs and general high-dimensional expanders. In doing so we give new tools to analyze Sum-of-Squares SDPs and connect the UGC to another important complexity theoretic conjecture, the Small-Set-Expansion Hypothesis. We also prove structural inequalities for high-dimensional expanders and give UG algorithms on these graphs. This talk is based on the joint works – https://arxiv.org/abs/2006.09969 and https://arxiv.org/abs/2011.04658.