STOC Test of Time Award

The 2025 STOC Test of Time Award recognizes papers published in the Proceedings of the Annual ACM Symposium on Theory of Computing. This is the fourth year of this annual award. There are three awards, targeting the STOC conferences 10, 20, and 30 years prior to the year in which the award is given. While there is a preference for papers in the target years (and nominations from those years are encouraged), in each of these award categories it is also possible to nominate STOC conference papers published up to four conferences earlier than the targeted conference. Thus, the 2025 STOC Test of Time Awards are for papers presented at the STOC conferences in 2011-2015, 2001-2005, and 1991–1995. The awards will be presented at STOC 2025.

Lists of Papers

Here are links to the DBLP pages for the STOC conferences whose papers are eligible for 2024:

Nomination Procedure

Nominations should be sent to stoc25.tot.award@acm.org with a subject line of “STOC Test of Time Award” no later than March 31, 2025. Nominations should contain an explanation of the impact of the nominated paper(s), including references to follow-on work. A nomination may be accompanied by up to three additional endorsement letters, which may be sent by the endorsers directly to the same email address with the same subject line. Self-nominations are disallowed.

Selection

The winners will be selected by a committee appointed by the SIGACT Executive Committee. For 2024 the selection committee consists of Sandy Irani (chair, UC Irvine) , Ran Canetti (Boston U), Mike Paterson (Warwick), and David Shmoys (Cornell).

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 but not limited to:

Opening up a new area of research
Introducing new techniques
Solving a problem of lasting importance
Stimulating advances in other areas of computer science or in other disciplines.

The committee expects to select exactly one paper for each award. However, when circumstances justify it, up to three may be selected. The committee will consider papers that were not explicitly nominated and gather additional input from experts, but formal nominations are extremely helpful in the committee’s deliberations and strongly encouraged.

Winners

2024

(30 years) Y. Azar, A.Z. Broder, A.R. Karlin, and E. Upfal, “Balanced Allocations”, 1994.
(30 years) M.X. Goemans and D.P. Williamson, “. 878-Approximation Algorithms for MAX CUT and MAX 2SAT”, 1994.
(30 years) R.M. Karp, U.V. Vazirani, V.V. Vazirani, “An Optimal Algorithm for On-line Bipartite Matching”, 1990.
(20 years) S. Har-Peled and S. Mazumdar, “On Coresets for k-Means and k-Median Clustering”, 2004.
(20 years) J. Kleinberg, “The Small-World Phenomenon: An Algorithmic Perspective”, 2000.
(10 years) A. Sahai and B. Waters, “How to Use Indistinguishability Obfuscation: Deniable Encryption, and More”, 2014.
(10 years) A. Dasgupta, R. Kumar, and T. Sarlós, “A Sparse Johnson-Lindenstrauss transform”, 2010.

2023

(30 years) Ajit Agrawal, Philip Klein, and R. Ravi, “When trees collide: An approximation algorithm for the generalized Steiner problem on networks”, 1989.
(30 years) Ethan Bernstein and Umesh Vazirani, “Quantum complexity theory”, 1993.
(20 years) Miklos Atjai, Ravi Kumar, and D. Sivakumar, “A sieve algorithm for the shortest lattice vector problem”, 2001.
(20 years) Oded Regev, “New lattice-based cryptographic constructions”, 2003.
(10 years) Kenneth L Clarkson and David P Woodruff, “Low rank approximation and regression in input sparsity time”, 2013.

2022

(30 years) Manuel Blum, Michael Luby, and Ronitt Rubinfeld, “Self-testing/correcting with applications to numerical problems”, 1990.
(30 years) Danny Dolev, Cynthia Dwork, and Moni Naor, “Non-malleable cryptography”, 1991.
(30 years) Noam Nisan, “Pseudorandom generators for space-bounded computation”, 1990.
(20 years) Moses Charikar, “Similarity estimation techniques from rounding algorithms”, 2002.
(20 years) Subhash Khot, “On the power of unique 2-prover 1-round games”, 2002.
(10 years) Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf, “Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds”, 2012.
(10 years) Craig Gentry, “Fully homomorphic encryption using ideal lattices”, 2009.

2021

(30 years) Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation”, 1988.
(30 years) David Chaum, Claude Crépeau, and Ivan Damgård, “Multiparty unconditionally secure protocols”, 1988.
(30 years) Tal Rabin and Michael Ben-Or, “Verifiable secret-sharing and multiparty protocols with honest majority”, 1989.
(20 years) Mark Jerrum, Alistair Sinclair, and Eric Vigoda, “A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries”, 2001.
(20 years) Daniel A. Spielman and Shang-Hua Teng, “Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time”, 2001.
(20 years) Mikkel Thorup and Uri Zwick, “Approximate distance oracles”, 2001.
(10 years) Scott Aaronson and Alex Arkhipov, “The computational complexity of linear optics”, 2011.