Johan Håstad receives the 2011 Gödel Prize

Publicerad 2012-01-18

The 2011 Gödel Prize is awarded to CIAM member Prof. Johan Håstad for his paper "Some optimal inapproximability results", Journal of the ACM, 48: 798--859, 2001.

The Gödel Prize for outstanding papers in the area of theoretical computer science is sponsored jointly by the European Association for Theoretical Computer Science (EATCS) and the Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery (ACM-SIGACT). This award is presented annually, with the presentation taking place alternately at the International Colloquium on Automata, Languages, and Programming (ICALP) and the ACM Symposium on Theory of Computing (STOC).

The 2011 Gödel Proze is awarded to Prof. Johan Håstad for his landmark paper "Some optimal inapproximability results", Journal of the ACM, 48: 798--859, 2001, in computational complexity. The paper specifically studies approximation properties of NP-hard problems. It improves on the PCP Theorem (recognized in a previous prize in 2001) to give novel probabilistic verifiers that can check membership proofs for NP languages while reading very few bits in them — as little as 3 bits. The existence of such verifiers implies that existing approximation algorithms for several problems such as MAX-3SAT cannot be improved if P is different from NP. In other words, there is a "threshold" approximation ratio which is possible to achieve in polynomial time, but improving upon which is NP-hard. Before this paper such "optimal" inapproximability results seemed beyond reach. The Fourier analytic techniques introduced in this paper have been adapted in dozens of other works, and are now taught in graduate courses in computational complexity. They also directly influenced subsequent work, such as the formulation of the unique games conjecture for proving further optimal inapproximability results, and lower bounds for geometric embeddings of metric spaces.

Till sidans topp