Test of Time Awards Winners
- 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.
- 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.
- Zvika Brakerski, Vinod Vaikuntanathan:
Efficient Fully Homomorphic Encryption from (Standard) LWE.
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.
Nominations should be sent by October 31, 2021 to firstname.lastname@example.org 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.
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.