Gödel Prize - 2001
Sanjeev Arora, Uriel Feige, Shafi Goldwasser, The 2001 Gödel Prize for outstanding journal articles in the area of theoretical computer science will be awarded to the authors of the following series of papers:
Carsten Lund, Laszlo Lovász, Ranjeev Motwani,
Shmuel Safra, Madhu Sudan, Mario Szegedy
"Interactive Proofs and the Hardness of Approximating Cliques"
Uriel Feige, Shafi Goldwasser, Laszlo Lovász, Shmuel Safra, and Mario Szegedy
Journal of the ACM 43 (1996), 268-292
"Probabilistic Checking of Proofs: A New Characterization of NP"
Sanjeev Arora and Shmuel Safra
Journal of the ACM 45 (1998), 70-122
"Proof Verification and the Hardness of Approximation Problems" In these three pathbreaking papers, the nine authors have developed a completely new understanding of when an algorithmic problem is "intrinsically hard". To clarify this is a central task of theoretical computer science. The basic idea of describing hard problems goes back to Kurt Gödel and is captured today in a problem class named NP. The first fundamental contribution of the prize winners is a description of NP by a new model of computation which integrates the idea of interacting computing agents and randomized computation. The authors obtained the remarkable and far-reaching result that the correctness of a solution can be checked by inspecting only very few bits of it when these bits are chosen by random. The second and equally strong contribution is concerned with a standard approach to solve hard problems, namely by allowing approximative solutions which would be easier to compute. The prize winners established the surprising fact that certain problems in NP remain hard even when only an approximative solutions is required. With their deep insights and powerful results, they have opened new perspectives for many problems in computer science, for example in optimization and cryptography.
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy
Journal of the ACM 45 (1998), 501-555