<div dir="ltr"><div dir="ltr"><div class="gmail_default" style="font-size:small"><div class="gmail_default"><p style="font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"> Wednesday, January 12th at<b> 11:00 am CT</b></font></font><br></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> </font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b> </font></font><font color="#000000">Zoom Virtual Talk (</font><font color="#0000ff"><b><a href="https://uchicagogroup.zoom.us/webinar/register/WN_A7XVyFbkQSePxM9HMBAzkw" target="_blank">register in advance here</a></b></font><font color="#000000">)</font></font></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font color="#000000"><b>Who: </b> </font><font color="#500050"> </font><font color="#000000"> </font></font></font></font>Mitali Bafna, Harvard University</p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b><br></b></p><p class="MsoNormal" style="margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b>Title:</b> </font><span style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;font-size:14px;letter-spacing:0.2px;white-space:pre-wrap">The Unique Games Conjecture: Sum-of-Squares Hierarchy and High-Dimensional Expansion</span><span style="font-family:arial,sans-serif"> </span><span style="font-family:arial,sans-serif"> </span></p><div><font face="arial, sans-serif"><br></font></div><div><b><font face="arial, sans-serif">Abstract: </font></b><font face="arial, sans-serif"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">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. </span></font></div><div><font face="arial, sans-serif"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">This talk is based on the joint </span><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">works -</span><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> </span><a href="https://www.google.com/url?q=https://arxiv.org/abs/2006.09969&sa=D&source=calendar&ust=1641852525649789&usg=AOvVaw2z3ld-g33NSqMoR_Y_B0Xm" target="_blank" style="color:rgb(26,115,232);letter-spacing:0.2px;white-space:pre-wrap">https://arxiv.org/abs/2006.<u></u>09969</a><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">, </span><a href="https://www.google.com/url?q=https://arxiv.org/abs/2011.04658&sa=D&source=calendar&ust=1641852525649789&usg=AOvVaw2N-HWYYz7B-OpNHelVbLyI" target="_blank" style="color:rgb(26,115,232);letter-spacing:0.2px;white-space:pre-wrap">https://arxiv.org/abs/<u></u>2011.04658</a><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> and </span><a href="https://www.google.com/url?q=https://arxiv.org/pdf/2111.09444.pdf&sa=D&source=calendar&ust=1641852525649789&usg=AOvVaw2VTLRj0NizJV-S79gkIxOP" target="_blank" style="color:rgb(26,115,232);letter-spacing:0.2px;white-space:pre-wrap">https://arxiv.org/pdf/2111.<u></u>09444.pdf</a><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> (currently under submission).</span></font></div><div><p class="MsoNormal" style="margin:0in;line-height:12pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="margin:0in;line-height:12pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p></div></div><div class="gmail_default"><font face="arial, sans-serif"><span style="color:rgb(17,17,17)"><b>Host</b>: </span><a href="mailto:madhurt@ttic.edu" target="_blank"><b>Madhur Tulsiani</b></a></font></div><br class="gmail-Apple-interchange-newline"></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div class="gmail_default" style="font-size:small"><br></div><div><div dir="ltr" class="gmail_signature" data-smartmail="gmail_signature"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Wed, Jan 5, 2022 at 9:57 PM Mary Marre <<a href="mailto:mmarre@ttic.edu">mmarre@ttic.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div><div><p style="font-size:small;font-variant-numeric:normal;font-variant-east-asian:normal;font-stretch:normal;line-height:normal;color:rgb(80,0,80);margin:0px"><font face="arial, sans-serif" color="#000000"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><b>When:</b> </font></font><font style="vertical-align:inherit"><font style="vertical-align:inherit"> Wednesday, January 12th at<b> 11:00 am CT</b></font></font><br></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif" color="#000000"> </font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="color:rgb(0,0,0);vertical-align:inherit"><font style="vertical-align:inherit"><b>Where:</b> </font></font><font color="#000000">Zoom Virtual Talk (</font><font color="#0000ff"><b><a href="https://uchicagogroup.zoom.us/webinar/register/WN_A7XVyFbkQSePxM9HMBAzkw" target="_blank">register in advance here</a></b></font><font color="#000000">)</font></font></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;color:rgb(80,0,80);line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><font style="vertical-align:inherit"><font style="vertical-align:inherit"><font color="#000000"><b>Who: </b> </font><font color="#500050"> </font><font color="#000000"> </font></font></font></font>Mitali Bafna, Harvard University</p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><b><br></b></p><p class="MsoNormal" style="font-size:small;margin:0in 0in 0.0001pt;line-height:normal;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><font face="arial, sans-serif"><b>Title:</b> </font><span style="color:rgb(60,64,67);font-family:Roboto,Arial,sans-serif;font-size:14px;letter-spacing:0.2px;white-space:pre-wrap">The Unique Games Conjecture: Sum-of-Squares Hierarchy and High-Dimensional Expansion</span><span style="font-family:arial,sans-serif"> </span><span style="font-family:arial,sans-serif"> </span></p><div style="font-size:small"><font face="arial, sans-serif"><br></font></div><div style="text-align:left"><b><font face="arial, sans-serif">Abstract: </font></b><font face="arial, sans-serif"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">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. </span></font></div><div style="text-align:left"><font face="arial, sans-serif"><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">This talk is based on the joint </span><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">works -</span><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> </span><a href="https://www.google.com/url?q=https://arxiv.org/abs/2006.09969&sa=D&source=calendar&ust=1641852525649789&usg=AOvVaw2z3ld-g33NSqMoR_Y_B0Xm" style="color:rgb(26,115,232);letter-spacing:0.2px;white-space:pre-wrap" target="_blank">https://arxiv.org/abs/2006.<u></u>09969</a><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap">, </span><a href="https://www.google.com/url?q=https://arxiv.org/abs/2011.04658&sa=D&source=calendar&ust=1641852525649789&usg=AOvVaw2N-HWYYz7B-OpNHelVbLyI" style="color:rgb(26,115,232);letter-spacing:0.2px;white-space:pre-wrap" target="_blank">https://arxiv.org/abs/<u></u>2011.04658</a><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> and </span><a href="https://www.google.com/url?q=https://arxiv.org/pdf/2111.09444.pdf&sa=D&source=calendar&ust=1641852525649789&usg=AOvVaw2VTLRj0NizJV-S79gkIxOP" style="color:rgb(26,115,232);letter-spacing:0.2px;white-space:pre-wrap" target="_blank">https://arxiv.org/pdf/2111.<u></u>09444.pdf</a><span style="color:rgb(60,64,67);letter-spacing:0.2px;white-space:pre-wrap"> (currently under submission).</span></font></div><div><p class="MsoNormal" style="text-align:left;margin:0in;line-height:12pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p><p class="MsoNormal" style="text-align:left;margin:0in;line-height:12pt;background-image:initial;background-position:initial;background-size:initial;background-repeat:initial;background-origin:initial;background-clip:initial"><br></p></div></div><div style="font-size:small"><font face="arial, sans-serif"><span style="color:rgb(17,17,17)"><b>Host</b>: </span><a href="mailto:madhurt@ttic.edu" target="_blank"><b>Madhur Tulsiani</b></a></font></div><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div style="font-size:small"><br></div><div><div dir="ltr"><div dir="ltr"><div><span style="font-family:arial,helvetica,sans-serif;font-size:x-small">Mary C. Marre</span><br></div><div><div><font face="arial, helvetica, sans-serif" size="1">Faculty Administrative Support</font></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1"><b>Toyota Technological Institute</b></font></i></div><div><i><font face="arial, helvetica, sans-serif" color="#3d85c6" size="1">6045 S. Kenwood Avenue</font></i></div><div><font size="1"><i><font face="arial, helvetica, sans-serif" color="#3d85c6">Chicago, IL 60637</font></i><br></font></div><div><b><i><a href="mailto:mmarre@ttic.edu" target="_blank"><font face="arial, helvetica, sans-serif" size="1">mmarre@ttic.edu</font></a></i></b></div></div></div></div></div></div>
</blockquote></div></div>