ACM Group Honors Pioneer in Computational Complexity with Second Gödel Prize

ACM Group Honors Pioneer in Computational Complexity with Second Gödel Prize

Sweden's Johan Håstad Lauded for Landmark Study on Approximation Properties of NP-Hard Problems

Association for Computing Machinery
Advancing Computing as a Science & Profession



Lance Fortnow           Virginia Gold
ACM SIGACT Chair           ACM
847-579-9310           212-626-0505
[email protected]          

[email protected]

 Printable PDF


NEW YORK, May 17, 2011 – ACM’s Special Interest Group on Algorithms and Computing Theory (SIGACT) has recognized Johan Håstad of Stockholm’s Royal Institute of Technology for introducing novel analytic techniques to the theory of the computational hardness of approximation. Håstad tackled a category of search problems known as NP-hard, which are unlikely to be solved by an absolute solution but may be addressed with approximation.  He improved on the PCP Theorem, a technique for creating proofs that can be verified very efficiently.  The recipient of the 1994 Gödel Prize for the switching lemma technique, which showed the limitations of small-depth circuits, Håstad will receive the 2011 Gödel Prize, sponsored jointly by SIGACT and the European Association for Theoretical Computer Science (EATCS), for outstanding papers in theoretical computer science at the ACM Symposium on the Theory of Computing (STOC) held as part of the Federated Computing Research Conference (FCRC), June 7, 2011, in San Jose, CA.

Probabilistically Checkable Proofs (PCPs) were developed by a team of collaborators who won the 2001 Gödel Prize. Håstad built on the PCP Theorem, which showed that every search problem has a proof that can be checked reading only a small number of bits.  Håstad’s novel verifiers can check membership proofs while reading as few as three bits in them, the best possible outcome.  Before Håstad published these novel findings in the Journal of the ACM in 2001 (, such “optimal” inapproximability results seemed beyond reach.  He introduced Fourier analytic techniques, which involve the process of decomposing a function into simpler pieces that have been adapted in many other works.  They are now taught in graduate courses in computational complexity.

A professor in theoretical computer science at the Royal Institute in Stockholm, Håstad was named the director of the Theory group in the School of Computer Science and Communication at the Institute.  He is a member of the Royal Swedish Academy of Science.  He received his BS in Mathematics at Stockholm University, and his MS in Mathematics at Uppsala University.  A graduate of the Massachusetts Institute of Technology with a Ph.D. in Mathematics, he won the ACM Doctoral Dissertation Award in 1986 ( ), among other prizes.

The Gödel Prize includes an award of $5,000, and is named in honor of Kurt Gödel, who was born in Austria-Hungary (now the Czech Republic) in 1906.  Gödel's work has had immense impact upon scientific and philosophical thinking in the 20th century.  The award recognizes his major contributions to mathematical logic and the foundations of computer science.


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.  




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. 



The European Association for Theoretical Computer Science is an international organization aimed at promoting research in the wide field of the foundations of computer science (ranging from formal languages, abstract computation models, algorithm design and complexity analysis, to applications of logic and semantics in programming).  It facilitates the exchange of ideas and results among computer scientists, in particular through the organization of the annual International Conference on Automata, Languages and Programming (ICALP).