[Theory] NOW: 1/12 Talks at TTIC: Mitali Bafna, Harvard University
Mary Marre
mmarre at ttic.edu
Wed Jan 12 10:59:26 CST 2022
*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 12, 2022 at 10:07 AM 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>*
>
>
> On Tue, Jan 11, 2022 at 3:48 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>*
>>
>>
>> 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/20220112/a2cbf1dc/attachment-0001.html>
More information about the Theory
mailing list