The Knuth Prize to Johan Håstad
ACM and the IEEE Computer Society have decided to award the Knuth Prize of 2018 to Johan Håstad, professor at the Department of Theoretical Computer Science. Håstad receives the award for his long and sustained record of milestone breakthroughs at the foundation of computer science with huge impact on many areas including optimization, cryptography, parallel computing, and complexity theory.
Congratulations on receiving the Knuth Prize! How does it feel to have won?
“It is very honoring! The previous recipients of this prize are very good researchers, so to join that group really makes me feel valued for my work. The amount of congratulations that I’ve received from colleagues all over the world is also very positive."
Tell us a bit about what are you are working on right now.
"My research area concerns which computational problems can be solved efficiently on a computer and which require too much resources when the input size increases. Some problems, the so called NP-complete problems, are, in general, too difficult to solve exactly but they often admit efficient algorithms if you lower the requirement of finding the absolutely best solution. I try to understand exactly how close to the optimal solution you can get by a provably efficient algorithm. My approach is mathematical in that I prove mathematical theorems about the quality of my algorithms as opposed to implementing them."
Contact
About the Knuth Prize
The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after Donald E. Knuth. The prize is awarded to individuals for their overall impact in the field.
The Knuth Prize has been awarded since 1996 and includes an award of $5000. The prize is awarded by ACM SIGACT and by IEEE Computer Society's Technical Committee on the Mathematical Foundations of Computing. Prizes are awarded in alternation at the ACM Symposium on Theory of Computing and at the IEEE Symposium on Foundations of Computer Science, which are among the most prestigious conferences in theoretical computer science.