Knuth Prize
![]() | This article has multiple issues. Please help or discuss these issues on the talk page. (Learn how and when to remove these template messages)
|
![](http://upload.wikimedia.org/wikipedia/commons/thumb/5/50/Strassen_Knuth_Prize_presentation.jpg/220px-Strassen_Knuth_Prize_presentation.jpg)
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth.
History[]
The Knuth Prize has been awarded since 1996 and includes an award of $5000. 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 alternation 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.
Winners[]
Since the prize was instituted in 1996, it has been awarded to:[3]
- 1996 – Andrew Yao[4]
- 1997 – Leslie Valiant[5]
- 1999 – László Lovász
- 2000 – Jeffrey Ullman
- 2002 – Christos Papadimitriou[6]
- 2003 – Miklós Ajtai[7][8]
- 2005 – Mihalis Yannakakis[9]
- 2007 – Nancy Lynch[10]
- 2008 – Volker Strassen[11]
- 2010 – David S. Johnson[2][12][13][14]
- 2011 – Ravi Kannan[15]
- 2012 – Leonid Levin[16]
- 2013 – Gary Miller[17]
- 2014 – Richard J. Lipton[18]
- 2015 – László Babai[19]
- 2016 – Noam Nisan[20]
- 2017 – Oded Goldreich[21]
- 2018 – Johan Håstad[22]
- 2019 – Avi Wigderson[23][24]
- 2020 – Cynthia Dwork[25][26][27]
- 2021 – Moshe Vardi[28][29]
Selection Committees[]
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.) |
See also[]
References[]
- ^ Knuth Prize, IEEE Computer Society
- ^ a b In Memoriam: David S. Johnson, Computing Research Association
- ^ "Knuth Prize". ACM SIGACT. September 23, 2021. Retrieved September 23, 2021.
- ^ SMU Panel Discussion on Creating the Future Through Computing with Distinguished Turing Award Panelists, Singapore Management University
- ^ Valiant Receives 2010 Turning Award (PDF), Notices of the American Mathematical Society (June/July 2011)
- ^ Bernadette Young (8 Oct 2019), Professor Christos Papadimitriou Awarded the 2018 Harvey Prize, Columbia University, Engineering
- ^ SIGACT Annual Report July 2002 - June 2003; 1. Awards that were given out, ACM, 2003
- ^ 2003 Knuth Prize Miklos Ajtai, ACM, October 9, 2003
- ^ 2005 Knuth Prize Mihalis Yannakakis, ACM, May 1, 2006
- ^ Nancy Lynch Named Recipient of ACM Award for Contributions to Reliability of Distributed Computing, MIT Computer Science & Artificial Intelligence Lab, 4 April 2007
- ^ ACM SIGACT 2008 Knuth Prize Recognizes Strassen for Contributions to Efficient Algorithm Design, ACM, October 23, 2008
- ^ Linda Crane, David S. Johnson: In Memoriam, Columbia University, Computer Science
- ^ Lee L. Keener, David S. Johnson '67, Amherst Magazine
- ^ AT&T Labs Researcher to Receive ACM SIGACT Knuth Prize for Algorithm Innovations, ACM, March 2, 2010
- ^ Three Microsoft India researchers named ACM fellow, Illinois Intelligencer, 9 December 2016
- ^ Citation: 2012 Knuth Prize (PDF), ACM, July 15, 2012
- ^ ACM Awards Knuth Prize to Creator of Problem-Solving Theory and Algorithms, ACM, April 4, 2013
- ^ "ACM Awards Knuth Prize to Pioneer for Advances in Algorithms and Complexity Theory". Association for Computing Machinery. September 15, 2014. Archived from the original on September 20, 2014.
- ^ 2015 Knuth Prize Citation for László Babai (PDF), ACM, May 17, 2015
- ^ ACM Awards Knuth Prize to Pioneer of Algorithmic Game Theory, ACM, September 8, 2016
- ^ 2017 Knuth prize is Awarded to Oded Goldreich (PDF), ACM, June 13, 2017
- ^ 2018 Knuth Prize is Awarded to Johan Håstad (PDF), ACM, August 6, 2018
- ^ Sue Gee (7 April 2019), Knuth Prize 2019 Awarded For Contributions To Complexity Theory
- ^ "Optimization, Complexity and Math ... using Gradient" - Knuth Prize Lecture, STOC 2019 - Avi Wigderson, March 3, 2020, archived from the original on 2021-12-14
- ^ Elizabeth Salazar (15 May 2020), Cynthia Dwork wins Knuth Prize for Outstanding Contributions to the Foundations of Computer Science, Harvard University
- ^ Leading authority on cryptography and data privacy receives Knuth Prize, American Association for the Advancement of Science, 2 June 2020
- ^ Knuth Prize Lecture - Cynthia Dwork, 25 November 2020, archived from the original on 2021-12-14
- ^ 2021 Knuth Prize is Awarded to Moshe Vardi (PDF), ACM, May 9, 2021
- ^ STOC 2021 - Knuth Prize talk: Logic and Computation – A Match Made in Heaven - Moshe Vardi, Jul 14, 2021, archived from the original on 2021-12-14
External links[]
- Theoretical computer science
- Computer science awards
- Donald Knuth
- IEEE society and council awards