# 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.)

**Recipients**

- 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

** Open Problems **

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.

Great as the Boneh-Franklin paper was, I somehow don’t see it as “advancing theory of computation”.

Maybe it would fit better for the Paris Kanellakis Theory and Practice Award?

I think you have a point there. But a great result is a great result.

Subhash Khot: On the Power of Unique 2-Prover 1-Round Games.

* Hastad’s tight bounds for approximating CLIQUE.

* Chazelle’s inverse-ackermann time MST.

* Clarkson’s randomized method for geometric algorithm analysis (beyond the 14 year window, but its influence in geometry is stupendous)

* Arora/Mitchell geometric TSP.

I could probably go on, but I’ll stop :). I guess the problem is the timeline in which the impact is felt. For example, in retrospect the Munro-Paterson paper on median finding in a “stream” setting showed remarkable foresight, but it took the field of streaming to come up before this paper was noticed and appreciated.

You have to consider the interaction with the other prizes… Madhu did win a Nevalinna prize for a combination of R-S codes and PCP, which is probably worth more than the Godel prize.

The complexity bias of the prize is very unfortunate, though (much beyond the fact that the Godel committees never heard of geometry, as Suresh notes).

The “complexity bias”? What about the “Track A” bias??? The single Track B paper that has ever won the prize is Vardi and Wolper’s paper on automata-theoretic model checking. (One might perhaps also categorize Halpern and Moses’s epistemic paper as Track B.)

The eligibility criteria for the Godel Award is supposed to encompass the themes of ICALP Tracks A and B, according to the regulations. However three of the six members of the award committee are chosen by SIGACT (in practice always Track A) and three by EATCS (which more or less nominates half and half, insofar as 3 is divisible by 2 🙂 ). The word on the street is that members vote along party lines, hence the current situation.

What “geometry bias”? That’s not what I was trying to say at all ! I think whenever a prize is given out, it’s not hard to list deserving authors who didn’t get a prize (think Nobel !). I think this is why many people have an aversion to awards: not because there are false positives, but because there are many false negatives.

I fail to see the claimed bias on the prize. While Richard’s list of non-winners above has a lot of complexity papers on it, over at least the last decade, the Godel prize itself has covered a very broad range of topics.

If you think that there is great work to be recognized it takes a bit of effort to gather together a few people to write nominations. If you don’t like the list and you haven’t nominated work, then you have no basis for complaint.

As far as the time-limit goes, one has to trade off been deserving work that has ‘waited its turn’ and newer work (like “Primes is in P”) . The change from 7 to 14 years also changed the start of that time from the journal date to the conference date so it is much less of a gap. By either standard, the Nisan and Wigderson papers missed their chances. Unless they win this year, it will be too late for Raz’s Parallel Repetition or Sudan’s List Decoding. However, the Boneh-Franklin paper on identity-based encryption and Weil pairing has many more years of eligibility.

The Godel prize has mostly been for journal papers on work that has stood the test of time. In contrast, we give conference best paper awards for work that is the hot item of the moment, often just as the work is being made public. I am beginning to think that it might be worth creating an intermediate award for the best theory journal paper published each year. (This came up in a discussion on the Complexity Blog about Vardi’s CACM editorial on conferences vs journals.)

I agree with most of what you said. But the “test of time” is not one of the measures. Some papers got the award almost immediately and others papers with huge impact have some how been overlooked.

Other papers that come to mind.

– Leighton-Rao on separators

– Goemans-Williamson on Max-Cut SDP

– Bartal on tree embeddings (no journal version)

If it ever makes it into journal form:

Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran: Cache-Oblivious Algorithms. FOCS 1999: 285-298

Yes, another great choice.

I stand by my opinion that there is an anti-algorithmic bias in the Godel prize. Here is my own list of forgotten papers.

This is a characteristic of all worthwhile prizes: there are always more deserving recipients than opportunities to award the prize (usually several times as many). It’s unavoidable, since if they were perfectly matched, random fluctuations would ensure that sometimes no deserving recipient would be available. So, unless you think the Goedel prize is often given to papers that don’t deserve it, you must believe plenty of great papers have been denied the prize.

The only way to avoid this is to establish prizes that can be awarded as often as a suitable candidate appears. However, I’d strongly recommend against it, since then the battles over who should get the prize would become enormous. With current prizes, the stakes are lower since everyone knows there’s a lot of chance involved and thus not receiving the prize cannot be considered an insult.

Why are theory prizes given so often to a paper? Goedel, Fulkerson, Best paper in conferences, Paul Beame’s suggestion above. Why not give prizes to people who made significant contributions? Often major progress is made over the course of several papers. I think that giving prizes to papers misses out on the really big achievements. Isn’t it the case that most prizes in other scientific disciplines are not given to a single paper?

Why are theory prizes given so often to a paper?Giving prizes to papers is actually more egalitarian. When you give them to people instead, there’s always a tendency to try to second-guess the results, for example, to overlook someone unexpected who has made a breakthrough on the grounds that they are a one-hit wonder due to luck. The fairest approach is to recognize great work whenever it occurs, and focusing on papers helps psychologically.

The theory community has plenty of other biases regarding giving prizes. (For example, conference best paper awards are much worse than test of time awards, since they promote fads, but TCS has mostly best paper awards.) However, giving a majority of awards to papers rather than people is a good thing.

Why not give prizes to people who made significant contributions? Often major progress is made over the course of several papers. I think that giving prizes to papers misses out on the really big achievements.What’s an example of a prize-worthy discovery published in several papers, none of which could individually win a prize? In practice, what typically happens is that the last paper wins the prize; earlier papers may end up winning a test of time award as well (and of course some prizes can be given for several related papers). One could imagine a revolution carried out in so many small steps that no step deserved a prize, but I can’t think of any examples offhand.

The bias in favor of later papers may be unfair if the papers have different authors. If you make a breakthrough that is not fully recognized by the world and hence does not win a best paper award, and then I use it to prove great results and do win such an award, then I bet you won’t be happy. This is one reason to decouple awards from conferences and to allow them to be given for several related papers. However, it’s irrelevant to the issue of papers vs. people.

Isn’t it the case that most prizes in other scientific disciplines are not given to a single paper?Maybe, but plenty of them are given for a single discovery. For example, that’s one crucial difference between the Nobel prize (which is always given for a specific, single discovery) and the Turing award (which is more of a lifetime achievement award in practice).

I’d be happy to switch from single-paper to single-discovery prizes in TCS, especially if it meant de-emphasizing conference best paper awards.