View source for Knuth Prize

{{Short description|Prize given by ACM and IEEE for outstanding contributions to the foundations of computer science}}
[[File:Strassen Knuth Prize presentation.jpg|thumb|upright|[[Gary Miller (professor)|Gary Miller]] presents [[Volker Strassen]] with the 2008 Knuth Prize at SODA 2009.]]
The '''Donald E. Knuth Prize''' is a prize for outstanding contributions to the foundations of [[computer science]], named after the American computer scientist [[Donald Knuth|Donald E. Knuth]].

==History==
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.<ref>{{citation|url=https://tc.computer.org/tcmf-demo/awards/knuth-prize/|title=Knuth Prize|publisher=IEEE Computer Society}}</ref>
For instance, David S. Johnson "used his Knuth Prize lecture to push for practical applications for algorithms."<ref name=JohnsonInMemoriam>{{citation|url=https://cra.org/crn/2016/04/david-s-johnson/|title=In Memoriam: David S. Johnson|date=April 2016 |publisher=Computing Research Association}}</ref>

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.

==Winners==
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):<ref>{{cite web | url = http://www.sigact.org/prizes/knuth.htm:l | title = Knuth Prize | publisher = ACM SIGACT | date = September 23, 2021 | access-date = September 23, 2021}}</ref>

{| class="wikitable sortable" style="border:2px solid darkgrey;"
! Year !! Laureate !! Citation
{{thickborder}}

| 1996
| {{sortname|Andrew|Yao}}
| "fundamental research in computational complexity"<ref>{{citation|url=https://www.smu.edu.sg/conference/116741?itemid=6531|title=SMU Panel Discussion on Creating the Future Through Computing with Distinguished Turing Award Panelists|publisher=Singapore Management University}}</ref>
|-
| 1997
| {{sortname|Leslie|Valiant}}
| "far-reaching contributions to the study of computational complexity, parallel computation, and learning theory"<ref>{{citation|url=https://www.ams.org/notices/201106/rtx110600833p.pdf|title=Valiant Receives 2010 Turing Award|publisher=Notices of the American Mathematical Society (June/July 2011)}}</ref>
|-
| 1999
| {{sortname|László|Lovász}}
| "enormous influence on the theory of algorithms" and "fundamental discoveries that have became standard tools in theoretical computer science"<ref>{{cite news| url=https://news.yale.edu/2021/03/29/2021-abel-prize-winner-was-yale-math-and-computer-science-mainstay-0 | title=2021 Abel Prize winner was a Yale math and computer science mainstay | work=[[Yale News]] | publisher=[[Yale University]] | first=Ji | last=Shelton | date=March 29, 2021 | accessdate=April 24, 2022 }}</ref>
|-
| 2000
| {{sortname|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"<ref>{{cite news| url=https://www.eurekalert.org/news-releases/875990 | title=ACM Turing Award honors innovators who shaped computer programming: Aho and Ullman developed tools and seminal textbooks used by millions of software programmers | work=[[EurekAlert!]] | publisher=[[American Association for the Advancement of Science|AAAS]] | first=Jim | last=Shelton | date=March 31, 2021 | accessdate=April 24, 2022 }}</ref>
|-
| 2002
| {{sortname|Christos|Papadimitriou}}
| "for longstanding and seminal contributions to the foundations of computer science"<ref>{{citation|url=https://www.engineering.columbia.edu/news/christos-papadimitriou-harvey-prize|title=Professor Christos Papadimitriou Awarded the 2018 Harvey Prize|author=Bernadette Young|publisher=Columbia University, Engineering|date=8 Oct 2019}}</ref>
|-
| 2003
| {{sortname|Miklós|Ajtai}}
| "for numerous ground-breaking contributions to Theoretical Computer Science"<ref>{{citation|url=https://www.acm.org/special-interest-groups/volunteer-resources/sgb/annual-reports/2002-annual-report-documents/sigact-annual-report#h-1.-awards-that-were-given-out|title=SIGACT Annual Report July 2002 – June 2003; 1. Awards that were given out|publisher=ACM|date=2003}}</ref><ref>{{citation|url=https://www.sigact.org/prizes/knuth/2003.html|title=2003 Knuth Prize Miklos Ajtai|publisher=ACM|date=October 9, 2003}}</ref>
|-
| 2005
| {{sortname|Mihalis|Yannakakis}}
| "for numerous ground-breaking contributions to Theoretical Computer Science"<ref>{{citation|url=https://www.sigact.org/prizes/knuth/2005.html|title=2005 Knuth Prize Mihalis Yannakakis|publisher=ACM|date=May 1, 2006}}</ref>
|-
| 2007
| {{sortname|Nancy|Lynch}}
| "for seminal and influential contributions to the theory of distributed computing"<ref>{{citation|url=https://www.csail.mit.edu/news/nancy-lynch-named-recipient-acm-award-contributions-reliability-distributed-computing|title=Nancy Lynch Named Recipient of ACM Award for Contributions to Reliability of Distributed Computing|publisher=MIT Computer Science & Artificial Intelligence Lab|date=4 April 2007}}</ref>
|-
| 2008
| {{sortname|Volker|Strassen}}
| "for his seminal and influential contributions to efficient algorithms"<ref>{{citation|url=https://www.acm.org/media-center/2008/october/acm-sigact-2008-knuth-prize-recognizes-strassen-for-contributions-to-efficient-algorithm-design|title=ACM SIGACT 2008 Knuth Prize Recognizes Strassen for Contributions to Efficient Algorithm Design|publisher=ACM|date=October 23, 2008}}</ref>
|-
| 2010
| {{sortname|David|Johnson|David S. Johnson}}
| "for his contributions to theoretical and experimental analysis of algorithms"<ref name=JohnsonInMemoriam/><ref>{{citation|url=https://www.cs.columbia.edu/2016/david-s-johnson-in-memoriam/|title=David S. Johnson: In Memoriam|author=Linda Crane|publisher=Columbia University, Computer Science}}</ref><ref>{{citation|url=https://www.amherst.edu/amherst-story/magazine/in_memory/1967/davidjohnson|title=David S. Johnson '67|author=Lee L. Keener|publisher=Amherst Magazine}}</ref><ref>{{citation|url=https://www.acm.org/media-center/2010/march/att-labs-researcher-to-receive-acm-sigact-knuth-prize-for-algorithm-innovations|title=AT&T Labs Researcher to Receive ACM SIGACT Knuth Prize for Algorithm Innovations|publisher=ACM|date=March 2, 2010}}</ref>
|-
| 2011
| {{sortname|Ravi|Kannan}}
| "provided theoretical computer science with many powerful new algorithmic techniques"<ref>{{citation|url=https://www.illinoisintelligencer.com/news/250056385/three-microsoft-india-researchers-named-acm-fellow|title=Three Microsoft India researchers named ACM fellow|publisher=Illinois Intelligencer|date=9 December 2016}}</ref>
|-
| 2012
| {{sortname|Leonid|Levin}}
| "in recognition of four decades of visionary research in complexity, cryptography, and information theory"<ref>{{citation|url=https://www.sigact.org/prizes/knuth/citation2012.pdf|title=Citation: 2012 Knuth Prize|publisher=ACM|date=July 15, 2012}}</ref>
|-
| 2013
| {{sortname|Gary|Miller|Gary Miller (computer scientist)}}
| "major impact on cryptography as well as number theory, parallel computing, graph theory, mesh generation for scientific computing, and linear system solving"<ref>{{citation|url=https://www.acm.org/media-center/2013/april/acm-awards-knuth-prize-to-creator-of-problem-solving-theory-and-algorithms|title=ACM Awards Knuth Prize to Creator of Problem-Solving Theory and Algorithms|publisher=ACM|date=April 4, 2013}}</ref>
|-
| 2014
| {{sortname|Richard|Lipton|Richard J. 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"<ref>{{cite web | url = http://www.acm.org/press-room/news-releases/2014/knuth-prize-2014 | archive-url = https://web.archive.org/web/20140920220414/http://www.acm.org/press-room/news-releases/2014/knuth-prize-2014 | url-status = dead | archive-date = September 20, 2014 | title = ACM Awards Knuth Prize to Pioneer for Advances in Algorithms and Complexity Theory | publisher = Association for Computing Machinery | date = September 15, 2014 }}</ref><ref>{{cite news| url=https://news.gatech.edu/news/2014/09/17/acm-ieee-taps-lipton-prestigious-knuth-prize | title=ACM, IEEE Taps Lipton for Prestigious Knuth Prize | work=News Center | publisher=[[Georgia Tech]] | first=Phillip | last=Tylor | date=2014 | accessdate=April 24, 2022 }}</ref>
|-
| 2015
| {{sortname|László|Babai}}
| "for his fundamental contributions to theoretical computer science, including algorithm design and complexity theory"<ref>{{citation|url=https://www.sigact.org/prizes/knuth/citation2015.pdf|title=2015 Knuth Prize Citation for László Babai|publisher=ACM|date=May 17, 2015}}</ref>
|-
| 2016
| {{sortname|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"<ref>{{citation|url=http://www.acm.org/media-center/2016/september/knuth-prize-2016|title=ACM Awards Knuth Prize to Pioneer of Algorithmic Game Theory|publisher=ACM|date=September 8, 2016}}</ref>
|-
| 2017
| {{sortname|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"<ref>{{citation|url=https://www.sigact.org/prizes/knuth/citation2017.pdf|title=2017 Knuth prize is Awarded to Oded Goldreich|publisher=ACM|date=June 13, 2017}}</ref>
|-
| 2018
| {{sortname|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"<ref>{{citation|url=https://www.sigact.org/prizes/knuth/citation2018.pdf|title=2018 Knuth Prize is Awarded to Johan Håstad|publisher=ACM|date=August 6, 2018}}</ref>
|-
| 2019
| {{sortname|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"<ref>{{citation|url=https://www.i-programmer.info/news/112-theory/12674-knuth-prize-2019-awarded-for-contributions-to-complexity-theory.html|title=Knuth Prize 2019 Awarded For Contributions To Complexity Theory|author=Sue Gee|date=7 April 2019}}</ref><ref>{{citation|url=https://www.youtube.com/watch?v=A8isyuauRnc |archive-url=https://ghostarchive.org/varchive/youtube/20211214/A8isyuauRnc |archive-date=2021-12-14 |url-status=live|title="Optimization, Complexity and Math ... using Gradient" – Knuth Prize Lecture, STOC 2019 – Avi Wigderson|date=March 3, 2020}}{{cbignore}}</ref>
|-
| 2020
| {{sortname|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."<ref>{{citation|url=https://www.iq.harvard.edu/news/cynthia-dwork-wins-knuth-prize-outstanding-contributions-foundations-computer|title=Cynthia Dwork wins Knuth Prize for Outstanding Contributions to the Foundations of Computer Science|author=Elizabeth Salazar|publisher=Harvard University|date=15 May 2020}}</ref><ref>{{citation|url=https://www.eurekalert.org/pub_releases/2020-06/afcm-lao060220.php|title=Leading authority on cryptography and data privacy receives Knuth Prize|publisher=American Association for the Advancement of Science|date=2 June 2020}}{{Dead link|date=June 2025 |bot=InternetArchiveBot |fix-attempted=yes }}</ref><ref>{{citation|url=https://www.youtube.com/watch?v=2wLNgSaLb8A |archive-url=https://ghostarchive.org/varchive/youtube/20211214/2wLNgSaLb8A |archive-date=2021-12-14 |url-status=live|title=Knuth Prize Lecture – Cynthia Dwork|date=25 November 2020}}{{cbignore}}</ref><ref>{{cite news| url=https://www.hpcwire.com/off-the-wire/harvard-professor-receives-prize-for-contributions-to-theoretical-computer-science/ | title=Harvard Professor Receives Prize for Contributions to Theoretical Computer Science | work=HPC Wire | date=June 2, 2020 | accessdate=April 24, 2022 }}</ref>
|-
| 2021
| {{sortname|Moshe|Vardi}}
| "for outstanding contributions that apply mathematical logic to multiple fundamental areas of computer science"<ref>{{citation|url=https://www.sigact.org/prizes/knuth/citation2021.pdf|title=2021 Knuth Prize is Awarded to Moshe Vardi|publisher=ACM|date=May 9, 2021}}</ref><ref>{{citation|url=https://www.youtube.com/watch?v=1OPDkMAK9Fw |archive-url=https://ghostarchive.org/varchive/youtube/20211214/1OPDkMAK9Fw |archive-date=2021-12-14 |url-status=live|title=STOC 2021 – Knuth Prize talk: Logic and Computation – A Match Made in Heaven – Moshe Vardi|date=Jul 14, 2021}}{{cbignore}}</ref><ref>{{cite news| url=https://jhvonline.com/moshe-vardi-wins-knuth-prize-p29149-89.htm | title=Moshe Vardi wins Knuth Prize | work=[[Jewish Herald-Voice]] | first=Jade | last=Boyd | date=May 27, 2021 | accessdate=April 24, 2022 }}</ref>
|-
| 2022
| {{sortname|Noga|Alon}}
| "for foundational contributions in combinatorics and graph theory and applications to fundamental topics in computer science"<ref>{{Cite web |title=2022 Knuth Prize Awarded to Noga Alon |url=https://www.sigact.org/prizes/knuth/citation2022.pdf |access-date=July 2, 2022 |website=ACM Special Interest Group on Algorithms and Computation Theory}}</ref>
|-
| 2023
| {{sortname|É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"<ref>{{Cite web |title=Tardos honored with 2023 Knuth Prize |url=https://news.cornell.edu/stories/2023/06/tardos-honored-2023-knuth-prize |access-date=June 24, 2023}}</ref>
|-
| 2024
| {{sortname|Rajeev|Alur}}
| for "outstanding contributions to the foundations of computer science for his introduction of novel models of computation which provide the theoretical foundations for analysis, design, synthesis, and verification of computer systems"<ref>{{Cite web|title=2024 Knuth Prize: Rajeev Alur|url=https://www.sigact.org/prizes/knuth/citation2024.html | access-date=August 8, 2024 |website=ACM Special Interest Group on Algorithms and Computation Theory}}</ref>
|-
|2025
|[[Micha Sharir]]
|for "seminal contributions to computational and discrete geometry, the development of algorithmic motion planning, transforming the field of computational geometry, and inspiring generations of researchers"<ref>{{Cite web |title=2025 Knuth Prize |url=https://www.sigact.org/prizes/knuth/citation2025.html |access-date=2025-05-21 |website=www.sigact.org}}</ref>
|}

==Selection Committees==
{|class="wikitable" width="auto"
|+
!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.)
|-
|2024
|Edith Cohen (Google/Tel Aviv U.), David Eppstein (Chair, UC Irvine), Monika Henzinger (IST Austria), Kurt Mehlhorn (Max Planck Institute), Salil Vadhan (Harvard U.), and Moshe Vardi (Rice U.)
|-
|2025
|Noga Alon (Princeton), Edith Cohen (Chair, Google/Tel Aviv U.), David Eppstein (UC Irvine), Valerie King (U. of Victoria), Salil Vadhan (Harvard U.), Moshe Vardi (Rice U.)
|}

==See also==
* [[List of computer science awards]]

==References==
{{reflist}}

==External links==
*[http://www.sigact.org/prizes/knuth.html Knuth Prize website]

{{Knuth Prize laureates|state=expanded}}
{{Donald Knuth navbox}}
{{Association for Computing Machinery}}
{{Institute of Electrical and Electronics Engineers}}

[[Category:Awards established in 1996]]
[[Category:Theoretical computer science]]
[[Category:Computer science awards]]
[[Category:Donald Knuth]]
[[Category:IEEE society and council awards]]
[[Category:Awards of the Association for Computing Machinery]]