[Theory] NOW: 5/24 TTIC Colloquium: Subhash Khot, New York University

[Mary Marre]

*When:*      Monday, May 24, 2021 at *11:10 am CT*



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



*Who: *       Subhash Khot, New York University


*Title:*       Hardness of Approximation: From the PCP Theorem to the
2-to-2 Games Theorem

*Abstract:* Computer scientists firmly believe that no algorithm can
efficiently compute optimal solutions to a class of problems called NP-hard
problems. For many NP-hard problems, even computing an approximately
optimal solution remains NP-hard. This phenomenon, known as the hardness of
approximation, has numerous connections to proof checking, optimization,
combinatorics, discrete Fourier analysis, and geometry.

The talk will provide an overview of these connections. It will address why
graph coloring is a computationally hard problem, how it is possible to
check a proof without even looking at it, why computer scientists love the
majority vote, and whether a shape exists that looks spherical as well as
cubical. It will explain how all this fits into a 30-year research program
starting with the foundational Probabilistically Checkable Proofs (PCP)
Theorem and leading to the recent 2-to-2 Games Theorem.

*Bio: *Subhash Khot is a professor of computer science at the Courant
Institute of Mathematical Sciences at New York University. His prior
affiliations include Princeton University (PhD), Institute for Advanced
Study (member), Georgia Tech (assistant professor) and University of
Chicago (visiting professor). His research centers on computational
complexity and its connections to geometry and analysis. He is a recipient
of the National Science Foundation’s Alan T. Waterman Award, the
International Mathematical Union’s Nevanlinna Prize, the Simons
Investigator Award, a MacArthur Fellowship, and is a Fellow of the Royal
Society.

*Host:  **Madhur Tulsiani* <madhurt at ttic.edu>
For more information on the colloquium series or to subscribe to the
mailing list, please see http://www.ttic.edu/colloquium.php


Mary C. Marre
Faculty Administrative Support
*Toyota Technological Institute*
*6045 S. Kenwood Avenue*
*Room 517*
*Chicago, IL  60637*
*p:(773) 834-1757*
*f: (773) 357-6970*
*mmarre at ttic.edu <mmarre at ttic.edu>*


On Mon, May 24, 2021 at 10:08 AM Mary Marre <mmarre at ttic.edu> wrote:

> *When:*      Monday, May 24, 2021 at *11:10 am CT*
>
>
>
> *Where:*     Zoom Virtual Talk (*register in advance here
> <https://uchicagogroup.zoom.us/webinar/register/WN_YaOQdWxNQAmyS6vdswL7sA>*
> )
>
>
>
> *Who: *       Subhash Khot, New York University
>
>
> *Title:*       Hardness of Approximation: From the PCP Theorem to the
> 2-to-2 Games Theorem
>
> *Abstract:* Computer scientists firmly believe that no algorithm can
> efficiently compute optimal solutions to a class of problems called NP-hard
> problems. For many NP-hard problems, even computing an approximately
> optimal solution remains NP-hard. This phenomenon, known as the hardness of
> approximation, has numerous connections to proof checking, optimization,
> combinatorics, discrete Fourier analysis, and geometry.
>
> The talk will provide an overview of these connections. It will address
> why graph coloring is a computationally hard problem, how it is possible to
> check a proof without even looking at it, why computer scientists love the
> majority vote, and whether a shape exists that looks spherical as well as
> cubical. It will explain how all this fits into a 30-year research program
> starting with the foundational Probabilistically Checkable Proofs (PCP)
> Theorem and leading to the recent 2-to-2 Games Theorem.
>
> *Bio: *Subhash Khot is a professor of computer science at the Courant
> Institute of Mathematical Sciences at New York University. His prior
> affiliations include Princeton University (PhD), Institute for Advanced
> Study (member), Georgia Tech (assistant professor) and University of
> Chicago (visiting professor). His research centers on computational
> complexity and its connections to geometry and analysis. He is a recipient
> of the National Science Foundation’s Alan T. Waterman Award, the
> International Mathematical Union’s Nevanlinna Prize, the Simons
> Investigator Award, a MacArthur Fellowship, and is a Fellow of the Royal
> Society.
>
> *Host:  **Madhur Tulsiani* <madhurt at ttic.edu>
> For more information on the colloquium series or to subscribe to the
> mailing list, please see http://www.ttic.edu/colloquium.php
>
>
>
>
>
> Mary C. Marre
> Faculty Administrative Support
> *Toyota Technological Institute*
> *6045 S. Kenwood Avenue*
> *Room 517*
> *Chicago, IL  60637*
> *p:(773) 834-1757*
> *f: (773) 357-6970*
> *mmarre at ttic.edu <mmarre at ttic.edu>*
>
>
> On Sun, May 23, 2021 at 3:16 PM Mary Marre <mmarre at ttic.edu> wrote:
>
>> *When:*      Monday, May 24, 2021 at *11:10 am CT*
>>
>>
>>
>> *Where:*     Zoom Virtual Talk (*register in advance here
>> <https://uchicagogroup.zoom.us/webinar/register/WN_YaOQdWxNQAmyS6vdswL7sA>*
>> )
>>
>>
>>
>> *Who: *       Subhash Khot, New York University
>>
>>
>> *Title:*       Hardness of Approximation: From the PCP Theorem to the
>> 2-to-2 Games Theorem
>>
>> *Abstract:* Computer scientists firmly believe that no algorithm can
>> efficiently compute optimal solutions to a class of problems called NP-hard
>> problems. For many NP-hard problems, even computing an approximately
>> optimal solution remains NP-hard. This phenomenon, known as the hardness of
>> approximation, has numerous connections to proof checking, optimization,
>> combinatorics, discrete Fourier analysis, and geometry.
>>
>> The talk will provide an overview of these connections. It will address
>> why graph coloring is a computationally hard problem, how it is possible to
>> check a proof without even looking at it, why computer scientists love the
>> majority vote, and whether a shape exists that looks spherical as well as
>> cubical. It will explain how all this fits into a 30-year research program
>> starting with the foundational Probabilistically Checkable Proofs (PCP)
>> Theorem and leading to the recent 2-to-2 Games Theorem.
>>
>> *Bio: *Subhash Khot is a professor of computer science at the Courant
>> Institute of Mathematical Sciences at New York University. His prior
>> affiliations include Princeton University (PhD), Institute for Advanced
>> Study (member), Georgia Tech (assistant professor) and University of
>> Chicago (visiting professor). His research centers on computational
>> complexity and its connections to geometry and analysis. He is a recipient
>> of the National Science Foundation’s Alan T. Waterman Award, the
>> International Mathematical Union’s Nevanlinna Prize, the Simons
>> Investigator Award, a MacArthur Fellowship, and is a Fellow of the Royal
>> Society.
>>
>> *Host:  **Madhur Tulsiani* <madhurt at ttic.edu>
>> For more information on the colloquium series or to subscribe to the
>> mailing list, please see http://www.ttic.edu/colloquium.php
>>
>>
>>
>>
>>
>> Mary C. Marre
>> Faculty Administrative Support
>> *Toyota Technological Institute*
>> *6045 S. Kenwood Avenue*
>> *Room 517*
>> *Chicago, IL  60637*
>> *p:(773) 834-1757*
>> *f: (773) 357-6970*
>> *mmarre at ttic.edu <mmarre at ttic.edu>*
>>
>>
>> On Mon, May 17, 2021 at 6:39 PM Mary Marre <mmarre at ttic.edu> wrote:
>>
>>> *When:*      Monday, May 24, 2021 at *11:10 am CT*
>>>
>>>
>>>
>>> *Where:*     Zoom Virtual Talk (*register in advance here
>>> <https://uchicagogroup.zoom.us/webinar/register/WN_YaOQdWxNQAmyS6vdswL7sA>*
>>> )
>>>
>>>
>>>
>>> *Who: *       Subhash Khot, New York University
>>>
>>>
>>> *Title:*       Hardness of Approximation: From the PCP Theorem to the
>>> 2-to-2 Games Theorem
>>>
>>> *Abstract:* Computer scientists firmly believe that no algorithm can
>>> efficiently compute optimal solutions to a class of problems called NP-hard
>>> problems. For many NP-hard problems, even computing an approximately
>>> optimal solution remains NP-hard. This phenomenon, known as the hardness of
>>> approximation, has numerous connections to proof checking, optimization,
>>> combinatorics, discrete Fourier analysis, and geometry.
>>>
>>> The talk will provide an overview of these connections. It will address
>>> why graph coloring is a computationally hard problem, how it is possible to
>>> check a proof without even looking at it, why computer scientists love the
>>> majority vote, and whether a shape exists that looks spherical as well as
>>> cubical. It will explain how all this fits into a 30-year research program
>>> starting with the foundational Probabilistically Checkable Proofs (PCP)
>>> Theorem and leading to the recent 2-to-2 Games Theorem.
>>>
>>> *Bio: *Subhash Khot is a professor of computer science at the Courant
>>> Institute of Mathematical Sciences at New York University. His prior
>>> affiliations include Princeton University (PhD), Institute for Advanced
>>> Study (member), Georgia Tech (assistant professor) and University of
>>> Chicago (visiting professor). His research centers on computational
>>> complexity and its connections to geometry and analysis. He is a recipient
>>> of the National Science Foundation’s Alan T. Waterman Award, the
>>> International Mathematical Union’s Nevanlinna Prize, the Simons
>>> Investigator Award, a MacArthur Fellowship, and is a Fellow of the Royal
>>> Society.
>>>
>>> *Host:  **Madhur Tulsiani* <madhurt at ttic.edu>
>>> For more information on the colloquium series or to subscribe to the
>>> mailing list, please see http://www.ttic.edu/colloquium.php
>>>
>>>
>>>
>>>
>>> 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/20210524/f96800a6/attachment-0001.html>