The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.
The Knuth Prize has been awarded since 1996 and includes an award of US$5,000. The prize is awarded by ACM SIGACT and by IEEE Computer Society's Technical Committee on the Mathematical Foundations of Computing. Prizes are awarded in alternating years at the ACM Symposium on Theory of Computing and at the IEEE Symposium on Foundations of Computer Science, which are among the most prestigious conferences in theoretical computer science. The recipient of the Knuth Prize delivers a lecture at the conference. [1] For instance, David S. Johnson "used his Knuth Prize lecture to push for practical applications for algorithms." [2]
In contrast with the Gödel Prize, which recognizes outstanding papers, the Knuth Prize is awarded to individuals for their overall impact in the field.
Since the prize was instituted in 1996, it has been awarded to the following individuals, with the citation for each award quoted (not always in full): [3]
| Year | Laureate | Citation |
|---|---|---|
| 1996 | Andrew Yao | "fundamental research in computational complexity" [4] |
| 1997 | Leslie Valiant | "far-reaching contributions to the study of computational complexity, parallel computation, and learning theory" [5] |
| 1999 | László Lovász | "enormous influence on the theory of algorithms" and "fundamental discoveries that have became standard tools in theoretical computer science" [6] |
| 2000 | Jeffrey Ullman | "sustained research contributions to Theoretical Computer Science, especially as it relates to applied areas of Computer Science such as compilers, parallelism, and databases; and for his contributions to Theoretical Computer Science education through textbooks and the mentoring of graduate students" [7] |
| 2002 | Christos Papadimitriou | "for longstanding and seminal contributions to the foundations of computer science" [8] |
| 2003 | Miklós Ajtai | "for numerous ground-breaking contributions to Theoretical Computer Science" [9] [10] |
| 2005 | Mihalis Yannakakis | "for numerous ground-breaking contributions to Theoretical Computer Science" [11] |
| 2007 | Nancy Lynch | "for seminal and influential contributions to the theory of distributed computing" [12] |
| 2008 | Volker Strassen | "for his seminal and influential contributions to efficient algorithms" [13] |
| 2010 | David Johnson | "for his contributions to theoretical and experimental analysis of algorithms" [2] [14] [15] [16] |
| 2011 | Ravi Kannan | "provided theoretical computer science with many powerful new algorithmic techniques" [17] |
| 2012 | Leonid Levin | "in recognition of four decades of visionary research in complexity, cryptography, and information theory" [18] |
| 2013 | Gary Miller | "major impact on cryptography as well as number theory, parallel computing, graph theory, mesh generation for scientific computing, and linear system solving" [19] |
| 2014 | Richard Lipton | "for inventing new computer science and mathematical techniques to tackle foundational and practical problems in a wide range of areas in graph algorithms, computaiton, communication, program testing, and DNA computing" [20] [21] |
| 2015 | László Babai | "for his fundamental contributions to theoretical computer science, including algorithm design and complexity theory" [22] |
| 2016 | Noam Nisan | "for fundamental and lasting contributions to theoretical computer science in areas including communication complexity, pseudo-random number generators, interactive proofs, and algorithmic game theory" [23] |
| 2017 | Oded Goldreich | "for fundamental and lasting contributions to theoretical computer science in many areas including cryptography, randomness, probabilistically checkable proofs, inapproximability, property testing as well as complexity theory in general" [24] |
| 2018 | Johan Håstad | "for his long and sustained record of milestone breakthroughs at the foundations of computer science, with huge impact on many areas including optimization, cryptography, parallel computing, and complexity theory" [25] |
| 2019 | Avi Wigderson | "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" [26] [27] |
| 2020 | Cynthia Dwork | "for fundamental and lasting contributions to computer science. Dwork is one of the most influential theoretical computer scientists of her generation. Her research has transformed several fields, most notably distributed systems, cryptography, and data privacy, and her current work promises to add fairness in algorithmic decision making to the list." [28] [29] [30] [31] |
| 2021 | Moshe Vardi | "for outstanding contributions that apply mathematical logic to multiple fundamental areas of computer science" [32] [33] [34] |
| 2022 | Noga Alon | "for foundational contributions in combinatorics and graph theory and applications to fundamental topics in computer science" [35] |
| 2023 | Éva Tardos | for "her extensive research contributions and field leadership, namely co-authoring an influential textbook, Algorithm Design, co-editing the Handbook of Game Theory, serving as editor-in-chief of the Journal of the ACM and the Society for Industrial and Applied Mathematics (SIAM) Journal of Computing and chairing program committees for several leading field conferences" [36] |
| Year | Selection Committee |
|---|---|
| 1996 | Ronald Graham, (Chair AT&T Research), Joe Halpern (IBM Almaden Research Center), Kurt Mehlhorn (Max-Planck-Institut für Informatik), Nicholas Pippenger (University of British Columbia), Eva Tardos (Cornell University), Avi Wigderson (Hebrew University) |
| 1997 | |
| 1999 | Allan Borodin, Ashok Chandra, Herbert Edelsbrunner, Christos Papadimitriou, Éva Tardos (chair), and Avi Wigderson |
| 2000 | |
| 2002 | |
| 2003 | |
| 2005 | Richard Ladner, Tom Leighton, Laci Lovasz, Gary Miller, Mike Paterson and Umesh Vazirani (chair) |
| 2007 | Mike Paterson (Chair), Tom Leighton, Gary Miller, Anne Condon, Mihalis Yannakakis, Richard Ladner |
| 2008 | |
| 2010 | |
| 2011 | |
| 2012 | |
| 2013 | |
| 2014 | |
| 2015 | Russell Impagliazzo, (Chair, UCSD), Uriel Feige, (The Weizmann Institute of Science), Michel Goemans (MIT), Johan H˚astad (KTH Royal Institute of Technology), Anna Karlin (U. of Washington), Satish B Rao (UC Berkeley) |
| 2016 | Allan Borodin (U. Toronto), Uri Feige (Weizmann Institute), Michel Goemans (MIT, chair), Johan H˚astad (KTH), Satish Rao (UC Berkeley) and Shang-Hua Teng (USC). |
| 2017 | Allan Borodin, (Chair, U. of Toronto), Avrim Blum (CMU), Shafi Goldwasser (MIT and Weizmann Institute), Johan H˚astad (KTH – Royal Institute of Technology), Satish Rao (UC Berkeley), and Shanghua Teng (USC) |
| 2018 | Allan Borodin, (U. of Toronto), Alan Frieze (CMU), Avrim Blum (TTIC), Shafi Goldwasser (UC Berkeley), Noam Nisan (Hebrew U.) and Shang-Hua Teng (Chair, USC) |
| 2019 | Avrim Blum (Chair, TTIC), Alan Frieze (CMU), Shafi Goldwasser (UC Berkeley), Noam Nisan (Hebrew U.), Ronitt Rubinfeld (MIT and Tel Aviv U.), and Andy Yao (Tsinghua U.). |
| 2020 | Alan Frieze, Chair(CMU), Hal Gabow (U. of Colorado), Noam Nisan (Hebrew U.), Ronitt Rubinfeld (MIT), Eva Tardos (Cornell U.), Andy Yao (Tsinghua U.) |
| 2021 | Harold Gabow (Chair, U. Colorado), Noam Nisan (Hebrew U.), Dana Randall (Georgia Tech), Ronitt Rubinfeld (MIT), Madhu Sudan (Harvard U.), and Andy Yao (Tsinghua U.) |
| 2022 | Harold Gabow (U. Colorado), Monika Henzinger (U. Vienna), Kurt Mehlhorn (Max Planck Institute), Dana Randall (Chair, Georgia Tech), Madhu Sudan (Harvard U.), and Andy Yao (Tsinghua U.) |
| 2023 | David Eppstein (UC Irvine), Monika Henzinger (Chair, ISTA/U. Vienna), Kurt Mehlhorn (Max Planck Institute), Dana Randall (Georgia Tech), Madhu Sudan (Harvard U.), and Moshe Vardi (Rice U.) |
Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.
Leonid Anatolievich Levin is a Soviet-American mathematician and computer scientist.
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.
Nancy Ann Lynch is a computer scientist affiliated with the Massachusetts Institute of Technology. She is the NEC Professor of Software Science and Engineering in the EECS department and heads the "Theory of Distributed Systems" research group at MIT's Computer Science and Artificial Intelligence Laboratory.
Paris Christos Kanellakis was a Greek American computer scientist.
Oded Goldreich is a professor of computer science at the faculty of mathematics and computer science of the Weizmann Institute of Science, Israel. His research interests lie within the theory of computation and are, specifically, the interplay of randomness and computation, the foundations of cryptography, and computational complexity theory. He won the Knuth Prize in 2017 and was selected in 2021 to receive the Israel Prize in mathematics.
ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.
Noga Alon is an Israeli mathematician and a professor of mathematics at Princeton University noted for his contributions to combinatorics and theoretical computer science, having authored hundreds of papers.
Ravindran Kannan is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of Computer Science and Automation Department of Indian Institute of Science.
Avi Wigderson is an Israeli mathematician and computer scientist. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural networks. Wigderson received the Abel Prize in 2021 for his work in theoretical computer science.
Moni Naor is an Israeli computer scientist, currently a professor at the Weizmann Institute of Science. Naor received his Ph.D. in 1989 at the University of California, Berkeley. His advisor was Manuel Blum.
Moshe Ya'akov Vardi is an Israeli mathematician and computer scientist. He is the Karen Ostrum George Distinguished Service Professor in Computational Engineering at Rice University, United States. and a faculty advisor for the Ken Kennedy Institute. His interests focus on applications of logic to computer science, including database theory, finite model theory, knowledge of multi-agent systems, computer-aided verification and reasoning, and teaching logic across the curriculum. He is an expert in model checking, constraint satisfaction and database theory, common knowledge (logic), and theoretical computer science.
Mihalis Yannakakis is professor of computer science at Columbia University. He is noted for his work in computational complexity, databases, and other related fields. He won the Donald E. Knuth Prize in 2005.
Larry Joseph Stockmeyer was an American computer scientist. He was one of the pioneers in the field of computational complexity theory, and he also worked in the field of distributed computing. He died of pancreatic cancer.
The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computing Machinery special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012.
The IEEE Annual Symposium on Foundations of Computer Science (FOCS) is an academic conference in the field of theoretical computer science. FOCS is sponsored by the IEEE Computer Society.
Cynthia Dwork is an American computer scientist best known for her contributions to cryptography, distributed computing, and algorithmic fairness. She is one of the inventors of differential privacy and proof-of-work.
Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.
Ronald Michiel de Wolf is a Dutch Computer Scientist, currently a Senior Researcher at Centrum Wiskunde & Informatica (CWI) and a professor at the Institute for Logic, Language and Computation (ILLC) of the University of Amsterdam (UvA).
Bakhadyr M. Khoussainov is a computer scientist and mathematician, who was born and educated in the Soviet Union, works in the fields of mathematical logic, computability theory, computable model theory and theoretical computer science. With Anil Nerode, he is the co-founder of the theory of automatic structures, which is an extension of the theory of automatic groups.