The following Test of Time Awards were given at STOC 2021.

The **30-year Test-of Time award** recognizes three seminal papers on information-theoretic secure multiparty computation, that were published in STOC 1988 and 1989:

- “Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation,” by Michael Ben-Or, Shafi Goldwasser and Avi Wigderson;
- “Multiparty Unconditionally Secure Protocols,” by David Chaum, Claude Cŕepeau and Ivan Damgård; and
- “Verifiable Secret Sharing and Multiparty Protocols with Honest Majority,” by Tal Rabin and Michael Ben-Or.

The **20-year Test-of-Time award** recognizes three seminal papers that were published in STOC 2001:

- “A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries” by Mark Jerrum, Alistair Sinclair and Eric Vigoda;
- “Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time” by Daniel Spielman and Shang-Hua Teng; and
- “Approximate distance oracles” by Mikkel Thorup and Uri Zwick.

The Spielman-Teng paper introduced the smoothed analysis of algorithms, a hybrid between worst-case and average-case analysis, and showed that the classical Simplex algorithm for Linear Programming has polynomial smoothed complexity (even though its worst case complexity is exponential). Smoothed analysis has been applied subsequently to a number of other algorithms for various problems, providing a way to go beyond traditional worst-case analysis and explain rigorously their performance in practice.

The Thorup-Zwick paper devised a space-efficient data structure for answering distance queries in a weighted graph with constant approximation in constant time. The algorithms are simple and easy to implement, and the space used is essentially optimal. The paper has had a great impact on subsequent work in the field, especially on the design of efficient data structures for metrics and graphs.

The **10-year Test-of-Time award** recognizes the following seminal paper that was published in STOC 2001.

- “The computational complexity of linear optics” by Scott Aaronson and Alex Arkhipov.

The Aaronson-Arkhipov paper put forward complexity-theoretic evidence that rudimentary quantum computers built entirely out of linear-optical elements cannot be efficiently simulated by classical computers. One of the paper’s lasting impacts lies in shifting the focus to sampling problems in the search for a provable super-polynomial “quantum advantage,” thereby providing the basis of several recent experimental efforts to demonstrate success in engineering quantum computers.

**Award Committee:**

Joseph Halpern (Cornell)

Salil Vadhan (Harvard)

Mihalis Yannakakis (Columbia)