ACM Special Interest Group on Algorithms and Computation Theory

STOC Test of Time Award

The 2021 STOC Test of Time Award recognizes papers published in the Proceedings of the Annual ACM Symposium on Theory of Computing. The award was inaugurated in 2021 and will be given annually thereafter. There are three awards, targeting the STOC conferences 10, 20, and 30 years prior to the year in which the award is given. 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 STOC conference papers published up to four conferences earlier than the targeted conference. Thus, the 2021 STOC Test of Time Awards will be for papers presented at the STOC conferences in 2007–2011, 1997–2001, and 1987–1991. The awards, which will be presented at STOC 2021, include a prize of US $500 per author as well as complimentary registration for all authors who attend the conference at which the award is given.

Lists of Papers

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



Nomination Procedure

Nominations should be sent to with a subject line of “STOC Test of Time Award” no later than May 24, 2021. 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.


The winners will be selected by a committee appointed by the SIGACT Executive Committee. For 2021 the selection committee consists of Joe Halpern (Cornell), Salil Vadhan (Harvard), and Mihalis Yannakakis (Columbia).

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:

  1. Opening up a new area of research
  2. Introducing new techniques
  3. Solving a problem of lasting importance
  4. 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 may consider awards to papers that are not nominated.



  • (30 years) Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson, “Completeness theorems for non-cryptographic fault-tolerant distributed computation”, STOC 1988.

  • (30 years) David Chaum, Claude Crépeau, and Ivan Damgård, “Multiparty unconditionally secure protocols”, STOC 1988.

  • (30 years) Tal Rabin and Michael Ben-Or, “Verifiable secret-sharing and multiparty protocols with honest majority”, STOC 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”, STOC 2001.

  • (20 years) Daniel A. Spielman and Shang-Hua Teng, “Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time”, STOC 2001.

  • (20 years) Mikkel Thorup and Uri Zwick, “Approximate distance oracles”, STOC 2001.

  • (10 years) Scott Aaronson and Alex Arkhipov, “The computational complexity of linear optics”, STOC 2011.