Thursday, February 11, 2016

Test of Time Award- a good idea but...

The ESA Conference (European Symposium on Algorithms) has a test-of-time award

recognizes outstanding papers in algorithms research that were published in the ESA proceedings 19-21 years ago and which are still influential and stimulating the field today.

This sounds like a great idea- some papers are more influential then people might have thought when they first got into ESA, and some papers are less influential then people might have thought. And I am happy that Samir Khuller (my chair) and Sudipto Guha (a grad student when the paper was written) won it for their paper Approximating Algorithms for Connected Dominating Sets.

But there are two things that are not quite right.

1) 19-21 years. That seems like a very small window.  '

2) The paper has to have been published in ESA.

Together this makes the job of the panel that decides the award easier as they only have to look at three years of conferences.  But there are many fine papers in algorithms that are not in ESA and there may be an awesome three year period and then a draught, so the window seems short.

But rather than complain let me ask some well defined questions:

Are there any other awards with a lower limit (in this case 19 years) on how long the paper has to be out, so that its influence can be better appreciated? This is a good idea, though 19 seems high.  Awards for a lifetime of work are often similar in that the are given after the works influence is known.

Are there any other awards that restrict themselves to ONE conference or journal? Of course best-paper and best-student-paper awards to that, but I don't know of any others.

ADDED LATER: A commenter says that there are LOTS of test-of-time awards associated to conferences:

see here

STOC, FOCS, SODA, CCC don't have them so I foolishly thought that was representative.
That raises another question - why do some conferences have it and some dont'?


  1. Erh... all test-of-time awards that I'm aware of restrict themselves to one conference. They are meant to counterbalance the best paper award, and the differences are often startling (see e.g. SIGCOMM conference).

  2. STOC/FOCS effectively have a shared test-of-time award called the Godel Prize...

    Have you considered sharing your thoughts with a trusted confidant before you make them public?

    1. The Godel prize goes to a paper that appeared in a refereed Journal within the last 14 years.

      This is not like the test-of-time awards that require a paper be in a specific journal and (at least for ETA) give a short window for when it had to appear.

    2. And the Godel Prize is definitely not restricted to STOC/FOCS papers. I actually like a conference-based prize, with a specific year in mind rather than a window. 10 years should be OK. I like the POPL version. 20 is just too long. The real question if you did this: How many of the Best Papers would also win this award. I certainly can think of plenty of highly deserving papers that were not recognized at the time, but is that the exception or the rule?

  3. The most influential POPL paper award is always given to a paper from POPL 10 years ago. (

  4. There is similar stuff in SIGSOFT/ICSE: Most Influential Paper award. Looks at papers from 10 years ago.

    What we should be asking is why the correlation between "Best Paper" (of that year) and "Most Influential" (10 years on) is so low.

  5. Congratulations Samir Khuller and Sudipto Guha! For most conferences where test of time award is given, the papers are selected from the accepted list of current-X year. It is good that ESA looks at 3 years span.

    Some other conferences where such award is given include TCC, PODS, LATIN, SIGMOD, VLDB etc.

  6. I'm surprised that there are award for EXACTLY 10 years ago since
    there could easily be too great papers in one year, and none in a different year.

    There are two paramters here:
    a) size of window. 3-years is prob good.
    b) amount of time that has to have passed. 19-21 seems long, 10 seems
    right to me.

    So I would suggest an award for best paper 9-11 years ago. Or since
    we are computer scientists, maybe 8-16 years ago so we can use base 2.

    1. The amount of time depends on what kind of impact you're interested in. 10 years is probably enough to see the impact in TCS, while it's better to wait for 20 years to see how the paper affected the wider CS and other computational fields. For seeing the impact on the rest of the society, you'll probably have to wait for at least 30 or 40 years.

      For an example, the original paper describing the FM-index was published in FOCS 2000. By 2010, it had spawned a successful research direction with hundreds of papers and many promising applications. Today the FM-index is one of the core tools in bioinformatics, with new applications being discovered all the time.

      Or consider public-key cryptosystems. The fundamental papers were published in the late 1970s, but the world was starting to see their real impact only around 2000.

  7. TCC (theory of cryptography) has a test-of-time award. Papers published at least 8 years ago at the conference:

  8. LICS has had a Test-of-Time Award since 2006. See here. The LICS Test-of-Time Award recognizes up to three papers from the LICS proceedings from 20 years prior.