[Theory] 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*
*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/20210517/e9d052c9/attachment.html>