Subhash Khot, Ph.D.New York University
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.
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.