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

acm
Association for Computing Machinery
Advancing Computing as a Science & Profession

Contacts:

 

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 (http://dx.doi.org/10.1145/502090.502098), 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 (http://awards.acm.org/doctoral_dissertation/ ), 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 20^th century.  The award recognizes his major contributions to mathematical logic and the foundations of computer science.

 

About ACM

ACM, the Association for Computing Machinery www.acm.org, 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.  

 

 

About SIGACT

The ACM Special Interest Group on Algorithms and Computation Theory http://sigact.acm.org 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 EATCS

The European Association for Theoretical Computer Science http://eatcs.org 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).