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

  • Speaker
  • Subhash Khot, Ph.D.New York University
Date & Time

About Mathematics and Physical Sciences

Mathematics and Physical Sciences lectures are open to the public and are held at the Gerald D. Fischbach Auditorium at the Simons Foundation headquarters in New York City. Tea is served prior to each lecture.

View all Lectures in This 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

Khot is a professor of computer science at the Courant Institute of Mathematical Sciences at New York University. His prior appointments include Georgia Tech and the University of Chicago. He holds a Ph.D. from Princeton University. Khot’s 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.
Advancing Research in Basic Science and MathematicsSubscribe to our newsletters to receive news & updates