Symposium on Theory of Computing

Last updated

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]

Contents

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

Related Research Articles

<span class="mw-page-title-main">Stephen Cook</span> American-Canadian computer scientist, contributor to complexity theory

Stephen Arthur Cook is an American-Canadian computer scientist and mathematician who has made significant contributions to the fields of complexity theory and proof complexity. He is a university professor emeritus at the University of Toronto, Department of Computer Science and Department of Mathematics.

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.

In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP, then for many important problems it is not only impossible to get an exact solution in polynomial time, but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.

<span class="mw-page-title-main">Leslie Valiant</span> British American computer scientist

Leslie Gabriel Valiant is a British American computer scientist and computational theorist. He was born to a chemical engineer father and a translator mother. He is currently the T. Jefferson Coolidge Professor of Computer Science and Applied Mathematics at Harvard University. Valiant was awarded the Turing Award in 2010, having been described by the A.C.M. as a heroic figure in theoretical computer science and a role model for his courage and creativity in addressing some of the deepest unsolved problems in science; in particular for his "striking combination of depth and breadth".

ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer.

<span class="mw-page-title-main">Knuth Prize</span> Prize given by ACM and IEEE for outstanding contributions to the foundations of computer science

The Donald E. Knuth Prize is a prize for outstanding contributions to the foundations of computer science, named after the American computer scientist Donald E. Knuth.

Umesh Virkumar Vazirani is an Indian–American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.

Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments.

Frances Foong Chu Yao is a Taiwanese-American mathematician and theoretical computer scientist. She is currently a Chair Professor at the Institute for Interdisciplinary Information Sciences (IIIS) of Tsinghua University. She was Chair Professor and Head of the Department of computer science at the City University of Hong Kong, where she is now an honorary professor.

The ACM Symposium on Principles of Distributed Computing (PODC) is an academic conference in the field of distributed computing organised annually by the Association for Computing Machinery.

The IEEE Annual Symposium on Foundations of Computer Science (FOCS) is an academic conference in the field of theoretical computer science. FOCS is sponsored by the IEEE Computer Society.

<span class="mw-page-title-main">Ran Raz</span>

Ran Raz is a computer scientist who works in the area of computational complexity theory. He was a professor in the faculty of mathematics and computer science at the Weizmann Institute. He is now a professor of computer science at Princeton University.

Ashok K. Chandra was a computer scientist at Microsoft Research in Mountain View, California, United States, where he was a general manager at the Internet Services Research Center. Chandra received his PhD in Computer Science from Stanford University, an MS from University of California, Berkeley, and a BTech from IIT Kanpur. He was previously Director of Database and Distributed Systems at IBM Almaden Research Center.

Amos Fiat is an Israeli computer scientist, a professor of computer science at Tel Aviv University. He is known for his work in cryptography, online algorithms, and algorithmic game theory.

<span class="mw-page-title-main">Noam Nisan</span> Israeli computer scientist

Noam Nisan is an Israeli computer scientist, a professor of computer science at the Hebrew University of Jerusalem. He is known for his research in computational complexity theory and algorithmic game theory.

Timothy Avelin Roughgarden is an American computer scientist and a professor of Computer Science at Columbia University. Roughgarden's work deals primarily with game theoretic questions in computer science.

Katrina Ligett is an American computer scientist. She is Associate Professor of computer science and economics at the Hebrew University and Visiting Associate at California Institute of Technology. She is known for work on algorithmic game theory and privacy.

Benjamin E. Rossman is an American mathematician and theoretical computer scientist, specializing in computational complexity theory. He is currently an associate professor of computer science and mathematics at Duke University.

Prasad Raghavendra is an Indian-American theoretical computer scientist and mathematician, working in optimization, complexity theory, approximation algorithms, hardness of approximation and statistics. He is a professor of computer science at the University of California at Berkeley.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.