Seminars
View all Seminars | Download ICal for this eventPlaying 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:
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.
This is based on joint work - https://arxiv.org/abs/2006.09969
Microsoft Teams Link:
https://teams.microsoft.com/l/meetup-join/19%3ameeting_ZGE3NDg5NzktMWQ0Zi00MzFmLTg5OTgtMTMyYWM4MWQyYjI2%40thread.v2/0?context=%7b%22Tid%22%3a%226f15cd97-f6a7-41e3-b2c5-ad4193976476%22%2c%22Oid%22%3a%227c84465e-c38b-4d7a-9a9d-ff0dfa3638b3%22%7d
For more details about the seminar please visit the website at https://www.csa.iisc.ac.in/iisc-msr-seminar/
Speaker Bio:
Host Faculty: Dr. Anand Louis