Seminars

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

Abstract:
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.
<br>
<br>
This is based on joint work - Link
<br>
<br>
Microsoft Teams Link:
<br>
<a href="Link
<br>
<br>
For more details about the seminar please visit the website at Link

Host Faculty: Dr. Anand Louis