| 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 InformationRelated ArticlesKnuth 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. 
Comments
or email your comment to: comments@i-programmer.info |
| Last Updated ( Friday, 17 August 2018 ) |
