Trailblazer in Computational Complexity Theory to Receive Knuth Prize
Håstad Cited for Milestone Breakthroughs in the Foundations of Computer Science
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 ACM 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 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.
Contact:
Samir Khuller
ACM SIGACT Chair
301-405-6765
[email protected]
Jim Ormond
ACM
212-626-0505
[email protected]