FOCS Test of Time Award

FOCS Test of Time Award Rules

The FOCS Test of Time Award recognizes papers published in past Annual IEEE Symposia on Foundations of Computer Science (FOCS) for their substantial, lasting, broad, and currently relevant impact. Papers may be awarded for their impact on Theory of Computing, or on Computer Science in general, or on other disciplines of knowledge, or on practice. The award is sponsored by the IEEE Computer Society Technical Committee on Mathematical Foundations of Computing (TCMF), and is presented annually at FOCS.

Selection Committee

Awarded papers are selected by a six member selection committee. Members of the selection committee are appointed by the FOCS Steering Committee by February of each year, starting 2019. Members are appointed to a two year term, but the first three members to be appointed will serve a one year term. Thus, at the end of each year half of the selection committee will be replaced. The steering committee also chooses each year one member of the selection committee to serve as its chair for that year.

Selection Process

The selection committee is free to choose any eligible paper or papers subject to the rules of eligibility. The committee is entitled to solicit nominations and recommendations, and may take responses into account.

Eligibility

For a paper to be eligible without being nominated, it must have been published in the Proceedings of the Annual IEEE Symposium on Foundations of Computer Science in one of three categories:

  1. ten conferences prior to the presentation of the award; or
  2. twenty conferences prior to the presentation of the award; or
  3. thirty conferences prior to the presentation of the award.

The committee may award in each category nominated papers published up to four conferences earlier, if it reaches the conclusion that the nominated papers were, due to constraints or neglect, not awarded by prior committees despite their obvious worthiness.

The committee is expected to select one paper from each of the three categories. However, in exceptional cases, the committee may select up to three papers from each category. Starting from the year 2029, the committee will be entitled to decline selecting papers from categories 2 and 3.

A paper may be awarded this award, in any category, at most once. Winning other prizes does not exclude a paper from winning this award.

To illustrate, for 2019, the committee can choose papers in the first category if they were published in FOCS 2009, in the second category if published in FOCS 1999, and in the third category if published in FOCS 1989. The committee is entitled to consider also nominated papers published in FOCS 2005-2008 in the first category, nominated papers published in FOCS 1995-1998 in the second category, and nominated papers published in FOCS 1985-1988 in the third category.

Award Winners

At FOCS 2024:

1994 award (citations):
Peter W. Shor:
Algorithms for quantum computation: discrete logarithms and factoring

Daniel R. Simon:
On the power of quantum computation

Michael Sipser, Daniel A. Spielman:
Expander Codes

2004 award (citations):
Subhash Khot, Guy Kindler, Elchanan Mossel, and Ryan O’Donnell:
Optimal Inapproximability results for Max-Cut and Other 2-Variables CSPs?

Daniele Micciancio:
Worst-case to average-case reductions based on Gaussian measures

2014 Award (citation):
Amir Abboud and Virginia Vassilevska Williams:
Popular conjectures imply strong lower bounds for dynamic problems

At FOCS 2023:

1993 Award (citation):
Alexander Barvinok:
A Polynomial Time Algorithm for Counting Integral Points in Polyhedra When the Dimension Is Fixed

2003 Award (citation):
Robert D. Kleinberg and Frank Thomson Leighton:
The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions

2013 Award (citation):
Sanjam Garg, Craig Gentry, Shai Halevi, Mariana Raykova, Amit Sahai, and Brent Waters:
Candidate Indistinguishability Obfuscation and Functional Encryption for All Circuits

At FOCS 2022:

2012 Awards (citation):
Niv Buchbinder, Moran Feldman, Joseph Naor, Roy Schwartz:
A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization

Yang Cai, Constantinos Daskalakis, S. Matthew Weinberg:
Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization

2002 Awards (citation):
Daniele Micciancio:
Generalized Compact Knapsacks, Cyclic Lattices, and Efficient One-Way Functions from Worst-Case Complexity Assumptions

Michael Luby:
LT Codes

1992 Awards (citation):
Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, Mario Szegedy:
Proof verification and hardness of approximation problems

Sanjeev Arora, Shmuel Safra:
Probabilistic checking of proofs: A new characterization of NP

Leonard J. Schulman:
Communication on Noisy Channels: A coding theorem for computation

At FOCS 2021:

1991 Awards:
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
Approximating Clique is Almost NP-Complete.

David Zuckerman:
Simulating BPP Using a General Weak Random Source.

Serge A. Plotkin, David B. Shmoys, Éva Tardos:
Fast Approximation Algorithms for Fractional Packing and Covering Problems.

2001 Award:
Ran Canetti:
Universally Composable Security: A New Paradigm for Cryptographic Protocols.

Boaz Barak:
How to Go Beyond the Black-Box Simulation Barrier.

Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao:
Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity.

2011 Award:
Zvika Brakerski, Vinod Vaikuntanathan:
Efficient Fully Homomorphic Encryption from (Standard) LWE.

At FOCS 2020:

1990 Awards (citation):
Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan:
Algebraic Methods for Interactive Proof Systems

Adi Shamir:
IP=PSPACE

László Babai, Lance Fortnow, Carsten Lund:
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols

2000 Award (citation):
Tim Roughgarden and Éva Tardos:
How bad is selfish routing?

2010 Award (citation):
Andreas Björklund:
Determinant Sums for Undirected Hamiltonicity

At FOCS 2019:

1989 Awards (citation):
Nathan Linial, Yishay Mansour, and Noam Nisan:
Constant Depth Circuits, Fourier Transform, and Learnability

Nick Littlestone and Manfred K. Warmuth:
The Weighted Majority Algorithm

Seinosuke Toda:
On the Computational Power of PP and ⊕P

1999 Award (citation):
Matteo Frigo, Charles Leiserson, Harald Prokop, Sridhar Ramachandran:
Cache-Oblivious Algorithms