Symposium on Theory of Computing

The Annual ACM Symposium on Theory of Computing (STOC) is an academic conference in the field of theoretical computer science. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the Association for Computing Machinery special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012.[1]

As Fich (1996) writes, STOC and its annual IEEE counterpart FOCS (the Symposium on Foundations of Computer Science) are considered the two top conferences in theoretical computer science,[2] considered broadly: they “are forums for some of the best work throughout theory of computing that promote breadth among theory of computing researchers and help to keep the community together.” Johnson (1984) includes regular attendance at STOC and FOCS as one of several defining characteristics of theoretical computer scientists.

Awards

The Gödel Prize for outstanding papers in theoretical computer science is presented alternately at STOC and at the International Colloquium on Automata, Languages and Programming (ICALP); the Knuth Prize for outstanding contributions to the foundations of computer science is presented alternately at STOC and at FOCS.

Since 2003, STOC has presented one or more Best Paper Awards[3] to recognize papers of the highest quality at the conference. In addition, the Danny Lewin Best Student Paper Award is awarded to the author(s) of the best student-only-authored paper in STOC.[4] The award is named in honor of Daniel M. Lewin, an American-Israeli mathematician and entrepreneur who co-founded Internet company Akamai Technologies, and was one of the first victims of the September 11 attacks.[5]

History

STOC was first organised on 5–7 May 1969, in Marina del Rey, California, United States. The conference chairman was Patrick C. Fischer, and the program committee consisted of Michael A. Harrison, Robert W. Floyd, Juris Hartmanis, Richard M. Karp, Albert R. Meyer, and Jeffrey D. Ullman.[6]

Early seminal papers in STOC include Cook (1971), which introduced the concept of NP-completeness (see also Cook–Levin theorem).

Location

STOC was organised in Canada in 1992, 1994, 2002, 2008, and 2017 in Greece in 2001, as a virtual/online conference in 2020 and 2021, and in Italy in 2022; all other meetings in 1969–2023 have been held in the United States. STOC was part of the Federated Computing Research Conference (FCRC) in 1993, 1996, 1999, 2003, 2007, 2011, 2015, 2019, and 2023.

Invited speakers

2004
Éva Tardos (2004), "Network games", Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04, pp. 341–342, doi:10.1145/1007352.1007356, ISBN 978-1581138528, S2CID 18249534
Avi Wigderson (2004), "Depth through breadth, or why should we attend talks in other areas?", Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04, p. 579, doi:10.1145/1007352.1007359, ISBN 978-1581138528, S2CID 27563516
2005
Lance Fortnow (2005), "Beyond NP: the work and legacy of Larry Stockmeyer", Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05, p. 120, doi:10.1145/1060590.1060609, ISBN 978-1581139600, S2CID 16558679
2006
Prabhakar Raghavan (2006), "The changing face of web search: algorithms, auctions and advertising", Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06, p. 129, doi:10.1145/1132516.1132535, ISBN 978-1595931344, S2CID 19222958
Russell Impagliazzo (2006), "Can every randomized algorithm be derandomized?", Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06, pp. 373–374, doi:10.1145/1132516.1132571, ISBN 978-1595931344, S2CID 22433370
2007
Nancy Lynch (2007), "Distributed computing theory: algorithms, impossibility results, models, and proofs", Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07, p. 247, doi:10.1145/1250790.1250826, ISBN 9781595936318, S2CID 22140755
2008
Jennifer Rexford (2008), "Rethinking internet routing", Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08, pp. 55–56, doi:10.1145/1374376.1374386, ISBN 9781605580470, S2CID 10958242
David Haussler (2008), "Computing how we became human", Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08, pp. 639–640, doi:10.1145/1374376.1374468, ISBN 9781605580470, S2CID 30452365
Ryan O'Donnell (2008), "Some topics in analysis of boolean functions", Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08, pp. 569–578, doi:10.1145/1374376.1374458, ISBN 9781605580470, S2CID 1241681
2009
Shafi Goldwasser (2009), "Athena lecture: Controlling Access to Programs?", Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09, pp. 167–168, doi:10.1145/1536414.1536416, ISBN 9781605585062
2010
David S. Johnson (2010), "Approximation Algorithms in Theory and Practice" (Knuth Prize Lecture)
2011
Leslie G. Valiant (2011), "The Extent and Limitations of Mechanistic Explanations of Nature" (2010 ACM Turing Award Lecture)
Ravi Kannan (2011), "Algorithms: Recent Highlights and Challenges" (2011 Knuth Prize Lecture)
David A. Ferruci (2011), "IBM's Watson/DeepQA" (FCRC Plenary Talk)
Luiz Andre Barroso (2011), "Warehouse-Scale Computing: Entering the Teenage Decade" (FCRC Plenary Talk)
2013
Gary Miller (2013), Knuth Prize Lecture
Prabhakar Raghavan (2013), Plenary talk
2014
Thomas Rothvoss (2014), "The matching polytope has exponential extension complexity"
Shafi Goldwasser (2014), "The Cryptographic Lens" (Turing Award Lecture) video
Silvio Micali (2014), "Proofs according to Silvio" (Turing Award Lecture) video
2015
Michael Stonebraker (2015), Turing Award Lecture video
Andrew Yao (2015), FCRC Keynote Lecture
László Babai (2015), Knuth Prize Lecture
Olivier Temam (2015), FCRC Keynote Lecture
2016
Santosh Vempala (2016), "The Interplay of Sampling and Optimization in High Dimension" (Invited Talk)
Timothy Chan (2016), "Computational Geometry, from Low to High Dimensions" (Invited Talk)
2017
Avi Wigderson (2017), "On the Nature and Future of ToC" (Keynote Talk)
Orna Kupferman (2017), "Examining classical graph-theory problems from the viewpoint of formal-verification methods" (Keynote Talk)
Oded Goldreich (2017), Knuth Prize Lecture

See also

Notes

  1. ^ "Proceedings of the 44th symposium on Theory of Computing". 2012. Retrieved 2012-09-17.
  2. ^ "Conference Ranks". Retrieved 2016-08-30.
  3. ^ "STOC Conference Best Paper Awards". Retrieved 2012-04-07.
  4. ^ "Danny Lewin Best Student Paper Award". Archived from the original on 2008-06-20.
  5. ^ Leighton, Tom (2002). "Remarks made by Tom Leighton to commemorate the naming of the STOC Best Student Paper Award in honor of the late Daniel Lewin".
  6. ^ Proc. STOC 1969. doi:10.1145/800169.

References