[Theory] 1/12 Talks at TTIC: Mitali Bafna, Harvard University

[Mary Marre]

*When:*      Wednesday, January 12th at* 11:00 am CT*



*Where:*     Zoom Virtual Talk (*register in advance here
<https://uchicagogroup.zoom.us/webinar/register/WN_A7XVyFbkQSePxM9HMBAzkw>*)


*Who: *       Mitali Bafna, Harvard University



*Title:*        The Unique Games Conjecture: Sum-of-Squares Hierarchy and
High-Dimensional Expansion

*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. My work studies unique games and related
problems (Small-set expansion, Max-Cut and Sparsest cut) from the lens of
the Sum-of-Squares (SoS) hierarchy, graph expansion and high-dimensional
expansion. We build algorithms for UG on a large class of restricted
instances (including high-dimensional expanders) and in doing so give new
tools to analyze Sum-of-Squares SDPs and connect the UGC to another
important complexity theoretic conjecture, the Small-Set-Expansion
Hypothesis. In another work we prove hypercontractive inequalities
on high-dimensional expanders, thus introducing tools to analyze small-set
expansion on such graphs. In this talk I will introduce the UGC, discuss
our progress on it and give some future directions in the area.
This talk is based on the joint works - https://arxiv.org/abs/2006.09969
<https://www.google.com/url?q=https://arxiv.org/abs/2006.09969&sa=D&source=calendar&ust=1641852525649789&usg=AOvVaw2z3ld-g33NSqMoR_Y_B0Xm>
, https://arxiv.org/abs/2011.04658
<https://www.google.com/url?q=https://arxiv.org/abs/2011.04658&sa=D&source=calendar&ust=1641852525649789&usg=AOvVaw2N-HWYYz7B-OpNHelVbLyI>
 and https://arxiv.org/pdf/2111.09444.pdf
<https://www.google.com/url?q=https://arxiv.org/pdf/2111.09444.pdf&sa=D&source=calendar&ust=1641852525649789&usg=AOvVaw2VTLRj0NizJV-S79gkIxOP>
(currently
under submission).



*Host*: *Madhur Tulsiani* <madhurt at ttic.edu>




Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Chicago, IL  60637*
*mmarre at ttic.edu <mmarre at ttic.edu>*
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20220105/2fee7c81/attachment.html>