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 Simons Foundation Lectures

Simons Foundation Lectures are free public colloquia related to basic science and mathematics. These high-level talks are intended for professors, students, postdocs and business professionals, but interested people from the metropolitan area are welcome as well.
Video Thumbnail

By clicking to watch this video, you agree to our privacy policy.

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