|Inaugural STOC Test Of Time Awards|
|Written by Sue Gee|
|Tuesday, 24 August 2021|
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
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:
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:
The 10-year Test-of-Time award recognized the following seminal paper that was published in STOC 2011.
[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.
or email your comment to: firstname.lastname@example.org
|Last Updated ( Tuesday, 24 August 2021 )|