Hardness of Approximation: From the PCP Theorem to the 2-to-2 Games Theorem
- Speaker
-
Subhash Khot, Ph.D.New York University
Presidential Lectures are a series of free public colloquia spotlighting groundbreaking research across four themes: neuroscience and autism science, physics, biology, and mathematics and computer science. These curated, high-level scientific talks feature leading scientists and mathematicians and are designed to foster discussion and drive discovery within the New York City research community. We invite those interested in these topics to join us for this weekly lecture series.
Researchers firmly believe that no algorithm can efficiently compute optimal solutions to computationally complex problems called NP-hard problems. For many NP-hard problems, even computing an approximately-optimal solution is NP-hard. This phenomenon, known as the hardness of approximation, has numerous connections to proof checking, optimization, combinatorics, discrete Fourier analysis, and geometry.
In this lecture, Subhash Khot will provide an overview of those connections. He will address why graph coloring is a computationally hard problem, how it is possible to check a proof without even looking at it, why computational scientists love the majority vote, and whether a shape exists that looks spherical as well as cubical. He 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.
About the Speaker
