View all Seminars  |  Download ICal for this event

Playing Unique Games on Certifiable Small-set Expanders

Series: Theory Seminar

Speaker: Mitali Bafna, PhD Student, Theoretical Computer Science, Harvard University

Date/Time: Jan 07 17:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor:

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 called certifiable small-set 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. The talk will start from a basic introduction to the UG problem and will not assume prior knowledge about UG or sum-of-squares algorithms.

This is based on joint work -

Microsoft Teams Link:

For more details about the seminar please visit the website at

Speaker Bio:

Host Faculty: Dr. Anand Louis