## 2019 Gödel Prize - LaudationThe 2019 Gödel Prize is awarded to
The PCP theorem is one of the most influential and impressive results of the theory of computation, having fundamental implication both to the study of the inherent difficulty of approximation problems and to the study of probabilistic proof systems. This paper provides an alternative proof of the PCP Theorem, which is fundamentally different from the original proof. The new proof is significantly simpler than the original, making its presentation in complexity courses a feasible task. In addition, it significantly improves on important parameters of the resulting PCP, yields the same improvements for locally testable codes, and has inspired much research including practical applications. Providing an alternative proof for a result of such importance is an achievement to celebrate, especially for a proof addressing issues that have been puzzling many researchers and resolving a central open problem in the area. Dinur's proof diverges from the original proof which relied on the arithmetization of NP. In this sense, the new proof is more direct and reveals new insights into the PCP Theorem and into NP. The proof is pivoted at the ``amplification'' of PCP systems, via a gradual process (of logarithmically many steps), while maintaining a direct connection with what is happening in terms of natural NP-complete problems. In fact, the amplification process is often described in terms of a natural Constraint Satisfaction Problem.
The Gödel Prize, awarded jointly by ACM SIGACT and EATCS, includes an award of USD 5,000. The prize is named in honor of Kurt Gödel, who was born in Austria-Hungary (now the Czech Republic) in 1906. Gödel's work has had immense impact upon scientific and philosophical thinking in the 20th century. The award recognizes his major contributions to mathematical logic and the foundations of computer science.
Anuj Dawar (Cambridge University) Robert Krauthgamer (Weizmann Institute) Joan Feigenbaum (Yale University) Giuseppe Persiano (Università di Salerno) Omer Reingold (Stanford University, chair) Daniel Spielman (Yale University). |