At the 2021 ACM Symposium on Theory of Computing (STOC), held online in June, sixteen recipients were honored in respect of seven papers presented at past STOC conferences  which have had a long-lasting impact and are thus deemed to have stood the test of time. The awardees each received a prize of US $500 per author, as well as complimentary registration to the conference.

STOC, Symposium on Theory of Computing, is the flagship conference of SIGACT, the ACM's Special Interest Group on Algorithms and Computation Theory.  It has been held annually since 1969 and covers all areas of research within Algorithms and Computation Theory. There are several well established SIGACT Prizes, including the Knuth Prize and the Gödel Prize and 2021 saw the introduction of a new set of awards for impactful past papers presented at the symposia and subsequently included in the published Proceedings.  

Like the already established HPCA Test of Time Award from the IEEE Computer Society in respect of past papers from the International Symposium of High Performance Computer Architecture (HPCA), the aim is to identify the contributions that have had a significant impact. Whereas the HPCA ToT award is for "at most one paper" per year of the award, SIGACT is expecting to recognize multiple papers and there are three awards, targeting the STOC conferences 30, 20 and 10 years prior to the year in which the award is given and it  was also possible to nominate STOC conference papers published up to four conferences earlier than the targeted conference. So in the inaugural year papers presented at the STOC conferences in 2007–2011, 1997–2001, and 1987–1991 were eligible. 

In selecting the Test of Time Award winners, the Committee paid particular attention to a paper's long-term impact, in particular 

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 following papers were those selected from among the nominations made for the inaugural awards in 2021. 

The 30-year Test-of Time award recognized 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.

These three papers address the 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 answer 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 while Rabin and Ben-Or showed that it could be done if n > 2t, provided there is a broadcast channel.

According to the judging panel:

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. 

The 20-year Test-of-Time award recognized 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
  [This] 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.
  
• “Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time” by Daniel Spielman and Shang-Hua Teng
  [This] 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.
  
  
• “Approximate distance oracles” by Mikkel Thorup and Uri Zwick.
  [This] 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 recognized the following seminal paper that was published in STOC 2011. 

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

[This] 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.

As we reported earlier this year, Aaronson was also the winner of the  2020 ACM Prize In Computing, the most recent to be awarded. for his "groundbreaking contributions to quantum computing" and contributions to complexity theory and this paper was mentioned alongside other relevant work.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info