Test of Time Awards Winners
- Uriel Feige, Shafi Goldwasser, László Lovász, Shmuel Safra, Mario Szegedy:
Approximating Clique is Almost NP-Complete.
FOCS 1991 - David Zuckerman:
Simulating BPP Using a General Weak Random Source.
FOCS 1991 - Serge A. Plotkin, David B. Shmoys, Éva Tardos:
Fast Approximation Algorithms for Fractional Packing and Covering Problems.
FOCS 1991 - Ran Canetti:
Universally Composable Security: A New Paradigm for Cryptographic Protocols.
FOCS 2001 - Boaz Barak:
How to Go Beyond the Black-Box Simulation Barrier.
FOCS 2001 - Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao:
Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity.
FOCS 2001 - Zvika Brakerski, Vinod Vaikuntanathan:
Efficient Fully Homomorphic Encryption from (Standard) LWE.
FOCS 2011
Call for Nominations
The 2021 FOCS Test of Time Awards recognize papers published in the Proceedings of the Annual IEEE Symposium on Foundations of Computer Science. The target years for the Test of Time Awards in 2021 are for papers presented at the FOCS conferences in 1991, 2001, and 2011, 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 87-90 can compete for the award targeting the 1991 conference and similar options are available for the other two awards.
Nomination Procedure
Nominations should be sent by October 31, 2021 to focs.tot.2021@gmail.com with a subject line of “FOCS Test of Time Award”. Nominations should contain an explanation of the impact of the nominated paper(s), including references to follow-on work. Self-nominations are discouraged.
Selection
The winners will be selected by a committee appointed by the FOCS Steering Committee, which for 2021 consists of Russell Impagliazzo (UCSD), Yael Kalai (MIT), Anna Karlin (U. Washington), Yishay Mansour (Tel Aviv U.), Mike Saks (Rutgers U.) and Luca Trevisan (Bocconi U., chair).
In selecting the Test of Time Award winners, the Committee will pay particular attention to long-term impact. This impact can come in many forms, including:
- Opening up a new area of research
- Introducing new techniques
- 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, if the committee will find that circumstances justify it, members may select up to three papers in each category, and include 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 third FOCS Test of Time Awards, which are annual awards.