2019 Gödel Prize - Laudation

The 2019 Gödel Prize is awarded to Prof. Irit Dinur for her proof of the PCP Theorem in the paper:

"The PCP theorem by gap amplification", Journal of the ACM, Vol 54 (3), Article 12, 2007. (preliminary version in the proceedings of the 38th Symposium on Theory of Computing, STOC 2006).

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.

Irit Dinur is a professor of computer science at the Weizmann Institute of Science. Her research is in computational complexity. She earned her doctorate in 2002 from Tel-Aviv University. She is the recipient of the 2007 Michael Bruno Memorial Award in Computer Science by Yad Hanadiv. She was a plenary speaker at the 2010 International Congress of Mathematicians. In 2012, she won the Anna and Lajos Erdős Prize in Mathematics.

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.

2019 Gödel Prize committee:

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).

e-max.it: your social media marketing partner
European Association for Theoretical Computer Science - Maintained and hosted by RU1 / CTI.