The Donald E. Knuth Prize for outstanding contributions to the foundations of computer science is awarded for major research accomplishments and contributions to the foundations of computer science over an extended period of time. The Prize is awarded annually by the ACM Special Interest Group on Algorithms and Computing Theory (SIGACT) and the IEEE Technical Committee on the Mathematical Foundations of Computing (TCMF).

**Criteria for Selection.** The winner was selected by a Prize
Committee consisting of six people appointed by the SIGACT and TCMF
Chairs: Avrim Blum (TTIC), Allan Borodin (U. Toronto),
Alan Frieze (CMU), Shafi Goldwasser (UC Berkeley), Noam Nisan (Hebrew U.),
and Shang-Hua Teng (USC, chair).

**About the Award.** The first Knuth Prize was presented at the 1996
ACM Symposium on Theory of Computing (STOC). Prize presentations now
alternate between STOC in odd years and the IEEE Symposium on Foundations
of Computer Science (FOCS) in even years. The winner is invited to give a
lecture at the conference.

The 2018 Prize will be presented at FOCS 2018 to be held in October 7-9, 2018, Paris, France. The Prize includes a $5000 award and a $1000 travel stipend (for travel to the award ceremony) that are paid by SIGACT and TCMF.

The previous Knuth Prize Laureates are: Andrew C.-C. Yao (1996), Leslie G. Valiant (1997), László Lovász (1999), Jeffery Ullman (2000), Christos Papadimitriou (2002), Miklos Ajtai (2003), Mihalis Yannakakis (2005), Nancy Lynch (2007), Volker Strassen (2008), David Johnson (2009), Ravindran Kannan (2011), Leonid Levin (2012), Gary Miller (2013), Richard Lipton (2014), László Babai (2015), Noam Nisan (2016), and Oded Goldreich (2017).

**About Donald E. Knuth.** The prize is named in honor and recognition
of the extraordinary accomplishments of Prof. Donald Knuth, Emeritus at
Stanford University. Prof. Knuth is best known for his ongoing multivolume
series, *The Art of Computer Programming*, which has played a
critical role in establishing and defining Computer Science as a rigorous,
intellectual discipline. Prof. Knuth has also made fundamental
contributions to the subfields of analysis of algorithms, compilers,
string matching, term-rewriting systems, literate programming, and
typography. His TeX and MF systems are widely accepted as standards for
electronic typesetting. Prof. Knuth's work is distinguished by its
integration of theoretical analyses and practical, real-world concerns. In
his work, theory and practice are not separate components of Computer
Science but rather inexorably linked branches of the same whole.

- 2018: Johan Håstad

- 2017: Oded Goldreich
- 2016: Noam Nisan
- 2015: László Babai
- 2014: Richard J. Lipton
- 2013: Gary L. Miller
- 2012: Leonid Levin
- 2011: Ravi Kannan
- 2010: David S. Johnson
- 2008: Volker Strassen
- 2007: Nancy Lynch
- 2005: Mihalis Yannakakis
- 2003: Miklos Ajtai
- 2002: Christos Papadimitriou
- 2000: Jeffrey D. Ullman
- 1999: László Lovász
- 1997: Leslie G. Valiant
- 1996: Andrew C.-C. Yao

Last updated 2018-08-15.