Communications of the ACM
Knuth Prize Awarded for Contributions to Computational Complexity
Johan Torkel Hastad has been named the recipient of the 2018 Donald E. Knuth Prize for his contributions to computational complexity theory.
Credit: I Programmer
Swedish researcher Johan Torkel Hastad has been named the recipient of the 2018 Donald E. Knuth Prize for his contribution to computational complexity theory.
The prize is given 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.
The ACM SIGACT announcement says Hastad was chosen 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."
Hastad also was recognized for three specific breakthroughs: switching lemma, in which he obtained an almost-optimal exponential lower bound on the size of constant-depth Boolean circuits for the parity function; his body of work in probabilistically checkable proofs and approximability of optimization problems; and his proof (written with several colleagues) that pseudorandom generators exist only if one-way functions exist.
From I Programmer
View Full Article
No entries found