[Theory] REMINDER: 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>*


On Wed, Jan 5, 2022 at 9:57 PM Mary Marre <mmarre at ttic.edu> wrote:

> *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/20220111/9f482572/attachment.html>