### 2011 Gödel Prize

The 2011 Gödel Prize is awarded to Johan T. Håstad for his paper:

Some optimal inapproximability results, Journal of the ACM, 48: 798--859, 2001.

This is a landmark paper in computational complexity, specifically, the
study of 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.

#### Award Committee

- Sanjeev Arora (Princeton)
- Josep Diaz (Universitat Politecnica de Catalunya)
- Cynthia Dwork (Microsoft Research)
- Mogens Nielsen (University of Aarhus)
- Mike Paterson (University of Warwick)
- Eli Upfal (Brown University)