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:
The three papers all consider the same basic question: how can a group of n agents, up to t of which may be corrupted, compute a function of their inputs while not revealing anything about the agents' inputs beyond what can be computed from the output of the function. These papers all answered this question without making any cryptographic or computational assumptions. Ben-Or, Goldwasser and Wigderson and Chaum, Cŕepeau and Damgård showed that this could be done if n > 3t; Rabin and Ben-Or showed that it could be done if n > 2t, provided there is a broadcast channel. These results had a profound impact, introducing tools that revolutionized not only the design of cryptographic protocols, but were also used in proving major complexity-theoretic results like the PCP theorem. The methods have also been making the transition to practice, with the development of commercial products that use the techniques of the nominated papers for applications ranging from distributed digital wallets for cryptocurrencies to privacy-preserving ML classification and training.
- “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:
The Jerrum-Sinclair-Vigoda paper gave a fully polynomial randomized approximation scheme for computing the permanent of a nonnegative matrix. The permanent plays a central role in the theory of hard counting problems and is important also in other fields like statistical physics. The JSV paper resolved the longstanding open problem of its fast approximate computation, and advanced the methodology of rapidly mixing Markov chains introduced in the 80’s by Jerrum and Sinclair.
- “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.
Joseph Halpern (Cornell)
Salil Vadhan (Harvard)
Mihalis Yannakakis (Columbia)