Knuth and Gödel Prizes to Be Awarded at 2019 ACM SIGACT Conference
Knuth Prize for Revolutionizing Understanding of Randomness in Computation; Gödel for Foundational Work on PCP Theorem
New York, NY, June 13, 2019—SIGACT, the Association for Computing Machinery’s Special Interest Group on Algorithms and Computation Theory, has announced that the Donald E. Knuth Prize will be awarded to Avi Wigderson and the Gödel Prize will be awarded to Irit Dinur. Wigderson and Dinur will be formally recognized at the 51st Annual Symposium on the Theory of Computing (STOC 2019) in Phoenix, Arizona, June 23-26.
Donald E. Knuth Prize
Avi Wigderson of the Institute for Advanced Study is recognized with the 2019 Donald E. Knuth Prize for fundamental and lasting contributions to the foundations of computer science in areas including randomized computation, cryptography, circuit complexity, proof complexity, parallel computation, and our understanding of fundamental graph properties.
In a series of results, Wigderson showed, under widely-believed computational assumptions, that every probabilistic polynomial time algorithm can be fully derandomized. In other words, randomness is not necessary for polynomial-time computation. In cryptography, Wigderson co-authored two landmark papers that showed how one could compute any function securely in the presence of dishonest parties. He was also part of a team that showed that all problems with short proofs (i.e., all problems in NP) in fact have zero-knowledge proofs: that is, proofs that yield nothing but their validity, a central cryptographic construct.
Wigderson received his PhD from Princeton University in 1983. He then served as a Visiting Assistant Professor at the University of California, Berkeley, a Visiting Scientist at IBM, and a Fellow at the Mathematical Sciences Research Institute (MSRI) in Berkeley before joining the Hebrew University as a faculty member in 1986. Since 1999, Wigderson has been a Professor in the School of Mathematics at the Institute for Advanced Study. Wigderson also received the Gödel Prize in 2009, for work with Omer Reingold and Salil Vadhan, and received the Nevanlinna Prize in 1994.
The Donald E. Knuth Prize recognizes outstanding contributions to the foundations of computer science by individuals for their overall impact in the field over an extended period. It is named in honor of Donald Knuth of Stanford University who has been called the “father of the analysis of algorithms.” The prize is jointly bestowed by the ACM Special Interest Group on Algorithms and Computation Theory (SIGACT) and the IEEE Computer Society Technical Committee on the Mathematical Foundations of Computing (TCMF).
Gödel Prize
The 2019 Gödel Prize is awarded to Irit Dinur of the Weizmann Institute of Science for her proof of the PCP Theorem in the paper “ The PCP Theorem by Gap Amplification .”
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. Dinur’s paper provides an alternative proof of the PCP Theorem, which is fundamentally different from the original proof. Her 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 a significant achievement, especially for a proof which addresses issues that have been puzzling many researchers and resolving a central open problem in the field.
Dinur received her PhD from Tel Aviv University. She later held appointments at the Institute of Advanced Study (Princeton, NJ), NEC, and the University of California, Berkeley before joining the Weizmann Institute of Science (Israel) as a Professor of Computer Science. Dinur won the Anna and Lajos Erdős Prize in Mathematics (2012) and a Michael Bruno Memorial Award (2007).
The Gödel Prize recognizes major contributions to mathematical logic and the foundations of computer science. 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 Gödel Prize is awarded jointly by ACM SIGACT and the European Association for Theoretical Computer Science (EATCS).
About ACM SIGACT
The ACM Special Interest Group on Algorithms and Computation Theory fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science. The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.
About ACM
ACM, the Association for Computing Machinery, is the world's largest educational and scientific computing society, uniting educators, researchers, and professionals to inspire dialogue, share resources, and address the field's challenges. ACM strengthens the computing profession's collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.
Contact:
Samir Khuller
ACM SIGACT Chair
301-405-6765
[email protected]
Jim Ormond
ACM
212-626-0505
[email protected]