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

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