Knuth Prize Awarded For Contributions To Computational Complexity
Written by Sue Gee   
Friday, 17 August 2018

Swedish theoretical computer scientist Johan Håstad has been named as the recipient of the 2018 Donald E. Knuth Prize for his contributions to computational complexity theory.

Named after Donald Knuth of Stanford University who has been called the "father of the analysis of algorithms"  and also dubbed the "Euclid of computer science", this annual prize was established in 1996 and includes an award of $5000. It is awarded to individuals for contributions to the foundations of computer science and 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) and is presented in alternation at the ACM Symposium on Theory of Computing and at the IEEE Symposium on Foundations of Computer Science (FOCS), which are among the most prestigious conferences in theoretical computer science.

This year's recipient is Johan Torkel Håstad, Professor of Computer Science of the KTH Royal Institute of Technology in Stockholm for:

his long and sustained record of milestone breakthroughs at the foundations of computer science, with major impact on many areas including optimization, cryptography, parallel computing, and complexity theory.


The ACM announcement states:

Håstad's multiple seminal works have not only resolved longstanding problems central to circuit lower bounds, pseudorandom generation, and approximability, but also introduced transformative techniques that have fundamentally influenced much of the subsequent work in these areas.

More details are provided in SIGACT's long-form citation which mentions three specific breakthroughs, two of which have previously been recognized by the Godel Prize, which he won in 1994 and 2011.

With his elegant switching lemma, he obtained an almost-optimal exponential lower bound on the size of constant-depth Boolean circuits for the parity function that ... had tremendous consequence to structural complexity theory.

Håstad’s body of work in probabilistically checkable proofs (PCP) and approximability of optimization problems has transformed the field. ... Håstad constructed almost optimal PCPs, where optimality holds with respect to parameters such as amortized free-bit complexity and total number of queries. 

Håstad’s joint paper with Russell Impagliazzo, Leonid Levin, and Michael 1 Luby, “A Pseudorandom Generator from any One-way Function” is a gem in complexity theory and cryptography .... [and] provided the ultimate result by proving that pseudorandom generators exist if and only if one-way functions exist. Thus, two fundamental phenomena in their most general and “pure” form — i.e., computational difficulty and pseudorandomness generation — are proved to be equivalent.

Professor Håstad will be presented with a certificate at the 59th Annual Symposium on Foundations of Computer Science (FOCS 2018) in Paris, France, October 7 - 9.

More Information

ACM announcement

SIGACT's long-form citation

Related Articles

Knuth Prize 2011 Goes To Microsoft Researcher 

Donald Knuth & The Art of Computer Programming

Donald Knuth At 80 Still Improving TAOCP 

Donald Knuth's Christmas Tree Lecture 2017

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on, Twitter, Facebook or Linkedin.



Foojay - All About Java and the OpenJDK

Tracking the OpenJDK is not an easy feat. It evolves rapidly under a release cycle of a new version every 6 months, hence there's hoards of new features, changes and bug fixes.This is where foojay ste [ ... ]

C# 9 and F# 5 Released With .NET 5

Microsoft has released C# 9 and F# 5 as part of the .NET 5 release this week. Visual Basic is also included in the 5.0 SDK. It does not include language changes, but has improvements to [ ... ]

More News





or email your comment to:

Last Updated ( Friday, 17 August 2018 )