image: Johan Håstad has been announced as the recipient of the 2018 Donald E. Knuth Prize for his contributions to computational complexity theory. view more
Credit: courtesy, KTH Royal Institute of Technology (Sweden)
NEW YORK, August 16, 2018 - The 2018 Donald E. Knuth Prize will be awarded to Johan Torkel Håstad 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.
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.
Håstad 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. Håstad'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 honor 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.
###
About SIGACT
The ACM Special Interest Group on Algorithms and Computation Theory fosters and promotes the discovery and dissemination of high quality research in the domain of theoretical computer science. The field includes algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.
About ACM
ACM, the Association for Computing Machinery, is the world's largest educational and scientific computing society, uniting computing educators, researchers and professionals to inspire dialogue, share resources and address the field's challenges. ACM strengthens the computing profession's collective voice through strong leadership, promotion of the highest standards, and recognition of technical excellence. ACM supports the professional growth of its members by providing opportunities for life-long learning, career development, and professional networking.