Test of Time Awards

1990 Awards
Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan
Algebraic Methods for Interactive Proof Systems.
FOCS 1990, pages 2-10.

Adi Shamir
IP=PSPACE.
FOCS 1990, pages 11-15.

László Babai, Lance Fortnow, Carsten Lund
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols.
FOCS 1990, pages 16-25.

2000 Award
Tim Roughgarden and Eva Tardos
How bad is selfish routing?
FOCS 2000, pages 93-102.

2010 Award
Andreas Björklund
Determinant Sums for Undirected Hamiltonicity.
FOCS 2010, pages 173-182.

Call for Nominations
The 2020 FOCS Test of Time Awards recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of Computer Science. These are the second such awards following the first awards given last year. The target years for the Test of Time Awards in 2020 are for papers presented at the FOCS conferences in 1990, 2000, and 2010, which are each considered for separate awards. While papers in the target years will always be considered by the award committee, in each of these award categories it is possible to nominate FOCS conference papers published up to four conferences earlier than the targeted conference. Thus, papers published at FOCS 86-89 can compete for the award targeting the 1990 conference and similar options are available for the other two awards.

Nomination Procedure
Nominations were sent to focs.test.2020@gmail.com with a subject line of “FOCS Test of Time Award” earlier this year. Nominations contained an explanation of the impact of the nominated paper(s), including references to follow-on work. Self-nominations are discouraged.

Selection
The winners were selected by a committee appointed by the FOCS Steering Committee, which for 2020 consists of Paul Beame (U. Washington, chair), Uri Feige (Weizmann Institute), Anna Karlin (U. Washington), Yishay Mansour (Tel Aviv U.), Claire Matthieu (C.N.R.S.), and Luca Trevisan (Bocconi U.).

In selecting the Test of Time Award winners, the Committee paid particular attention to long-term impact. This impact can come in many forms, including:

  1. Opening up a new area of research
  2. Introducing new techniques
  3. Solving a problem of lasting importance, among others.

The committee expects to select exactly one paper for the award associated with each targeted year, and expects to choose papers from those years. However, when the committee found that circumstances justified it, members selected up to three papers in each category, and included papers from up to four years prior to the targeted year. The committee is free to give awards to papers that are not nominated.

About the Awards
These are the second FOCS Test of Time Awards, which are annual awards. The 2020 award winners will be presented at FOCS 2020, held virtually, November 16-19, 2020.