Great Papers in Theory
Papers that the Gödel prize missed?
Kurt Godel’s name is attached to one of the great prizes that is given each year in computer science. The Godel Prize is given to the best paper that has advanced the theory of computation.
Since this is May 1st, the start of a new month, and end of our semester at Tech, I thought I would have a short post on this great prize. I want to say that I think the various committees have made terrific selections. Really. Here is the current list (from our friends at Wikipedia.)
- 1993 László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, and Charles Rackoff for the development of interactive proof systems
- 1994 Johan Håstad for an exponential lower bound on the size of constant-depth Boolean circuits
- 1995 Neil Immerman and Róbert Szelepcsényi for the Immerman–Szelepcsényi theorem regarding nondeterministic space complexity
- 1996 Mark Jerrum and Alistair Sinclair for work on Markov chains and the approximation of the permanent
- 1997 Joseph Halpern and Yoram Moses for defining a formal notion of “knowledge” in distributed environments
- 1998 Seinosuke Toda for Toda’s theorem which showed a connection between counting solutions (PP) and alternation of quantifiers (PH)
- 1999 Peter Shor for Shor’s algorithm for factoring numbers in polynomial time on a quantum computer
- 2000 Moshe Y. Vardi and Pierre Wolper for work on model checking with finite automata
- 2001 Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, and Mario Szegedy for the PCP theorem and its applications to hardness of approximation
- 2002 Géraud Sénizergues for proving that equivalence of deterministic pushdown automata is decidable
- 2003 Yoav Freund and Robert Schapire for the AdaBoost algorithm
- 2004 Maurice Herlihy, Mike Saks, Nir Shavit and Fotios Zaharoglou for applications of topology to the theory of distributed computing
- 2005 Noga Alon, Yossi Matias and Mario Szegedy for their foundational contribution to streaming algorithms
- 2006 Manindra Agrawal, Neeraj Kayal, Nitin Saxena for the AKS primality test
- 2007 Alexander Razborov, Steven Rudich for Natural Proofs
- 2008 Shanghua Teng, Daniel Spielman for Smoothed analysis of Algorithms
I am, however, surprised at some of the papers that have somehow been over looked and never awarded the prize. Here is a list of just five papers that I cannot understand how they could have been missed. Again nothing against the winners. I just am puzzled how these terrific papers did not get the recognition they deserve.
- Noam Nisan: Pseudorandom generators for space-bounded computation
- Noam Nisan, Avi Wigderson: Hardness vs Randomness
- Dan Boneh, Matthew K. Franklin: Identity-Based Encryption from the Weil Pairing
- Madhu Sudan: Decoding of Reed Solomon Codes beyond the Error-Correction Bound
- Ran Raz: A Parallel Repetition Theorem
Perhaps the main problem is the rules of the prize: (i) to be eligible, a paper must be published within the last 14 years; (ii) each year one paper wins. Maybe some years multiple papers can be awarded? Maybe the 14 year rule is too tight? It was once even shorter: 7 years.
I always end with an open problem. Today’s open problem is to fix these oversights. If you agree with me, then let’s make sure that these missed papers are properly recognized in the future. Perhaps you agree with me that papers have been missed, but not with my list. Either way, please let me know what you think.