16 Aug 2018 New York - The 2018 Donald E. Knuth Prize will be awarded to Johan Torkel Hastad of the KTH Royal Institute of Technology, Sweden 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 Knuth Prize 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). It will be presented at the 59th Annual Symposium on Foundations of Computer Science (FOCS 2018) in Paris, France, October 7-9.
Johan Hastad'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.
Johan Hastad is professor of computer science at the KTH Royal Institute of Technology in Stockholm, Sweden. He received his BS in Mathematics from Stockholm University, his MS in Mathematics from Uppsala University , and his PhD in Mathematics from MIT. Johan Hastad's honors include receiving the ACM Doctoral Dissertation Award (1986), the Gödel Prize (1994 and 2011), and the Göran Gustafsson Prize in Mathematics.
The Donald E. Knuth Prize is named in honour of Donald Knuth of Stanford University who has been called the "father of the analysis of algorithms". The annual award recognizes outstanding contributions to the foundations of computer science by individuals for their overall impact in the field over an extended period, and includes a $5,000 award.