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.
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.
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.
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:
- ten conferences prior to the presentation of the award; or
- twenty conferences prior to the presentation of the award; or
- 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.
At FOCS 2019:
Nathan Linial, Yishay Mansour, and Noam Nisan:
Constant Depth Circuits, Fourier Transform, and Learnability
Nick Littlestone and Manfred K. Warmuth:
The Weighted Majority Algorithm
On the Computational Power of PP and ⊕P
Matteo Frigo, Charles Leiserson, Harald Prokop, Sridhar Ramachandran:
At FOCS 2020:
Carsten Lund, Lance Fortnow, Howard J. Karloff, Noam Nisan:
Algebraic Methods for Interactive Proof Systems
László Babai, Lance Fortnow, Carsten Lund:
Non-Deterministic Exponential Time Has Two-Prover Interactive Protocols
Tim Roughgarden and Éva Tardos:
How bad is selfish routing?
Determinant Sums for Undirected Hamiltonicity
At FOCS 2021:
Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
Approximating Clique is Almost NP-Complete.
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.
Universally Composable Security: A New Paradigm for Cryptographic Protocols.
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.
Zvika Brakerski, Vinod Vaikuntanathan:
Efficient Fully Homomorphic Encryption from (Standard) LWE.