The Annual ACM Symposium on Theory of Computing (STOC) is an

academic conference An academic conference or scientific conference (also congress, symposium, workshop, or meeting) is an Convention (meeting), event for researchers (not necessarily academics) to present and discuss their scholarly work. Together with academic jou ...

in the field of

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

. STOC has been organized annually since 1969, typically in May or June; the conference is sponsored by the

Association for Computing Machinery The Association for Computing Machinery (ACM) is a US-based international learned society for computing. It was founded in 1947 and is the world's largest scientific and educational computing society. The ACM is a non-profit professional membe ...

special interest group SIGACT. Acceptance rate of STOC, averaged from 1970 to 2012, is 31%, with the rate of 29% in 2012. As writes, STOC and its annual

IEEE The Institute of Electrical and Electronics Engineers (IEEE) is an American 501(c)(3) organization, 501(c)(3) public charity professional organization for electrical engineering, electronics engineering, and other related disciplines. The IEEE ...

counterpart FOCS (the Symposium on Foundations of Computer Science) are considered the two top conferences in theoretical computer science, 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.” includes regular attendance at STOC and FOCS as one of several defining characteristics of theoretical computer scientists.

Awards

The

Gödel Prize 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 Inter ...

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 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. The award is named in honor of Daniel M. Lewin, an American-Israeli mathematician and entrepreneur who co-founded Internet company

Akamai Technologies Akamai Technologies, Inc. is an American company specialized in content delivery networkJ. Dilley, B. Maggs, J. Parikh, H. Prokop, R. Sitaraman, and B. Weihl. (CDN), cybersecurity, DDoS mitigation, and cloud services. It is headquartered in ...

, and was one of the first victims of the

September 11 attacks The September 11 attacks, also known as 9/11, were four coordinated Islamist terrorist suicide attacks by al-Qaeda against the United States in 2001. Nineteen terrorists hijacked four commercial airliners, crashing the first two into ...

History

STOC was first organised on 5–7 May 1969, in Marina del Rey,

California California () is a U.S. state, state in the Western United States that lies on the West Coast of the United States, Pacific Coast. It borders Oregon to the north, Nevada and Arizona to the east, and shares Mexico–United States border, an ...

United States The United States of America (USA), also known as the United States (U.S.) or America, is a country primarily located in North America. It is a federal republic of 50 U.S. state, states and a federal capital district, Washington, D.C. The 48 ...

. 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.Proc. STOC 1969. . Early seminal papers in STOC include , which introduced the concept of

NP-completeness In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

(see also

Cook–Levin theorem In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-completeness, NP-complete. That is, it is in NP (complexity), NP, and any problem in NP can be reducti ...

Location

STOC was organised in

Canada Canada is a country in North America. Its Provinces and territories of Canada, ten provinces and three territories extend from the Atlantic Ocean to the Pacific Ocean and northward into the Arctic Ocean, making it the world's List of coun ...

in 1992, 1994, 2002, 2008, and 2017 in

Greece Greece, officially the Hellenic Republic, is a country in Southeast Europe. Located on the southern tip of the Balkan peninsula, it shares land borders with Albania to the northwest, North Macedonia and Bulgaria to the north, and Turkey to th ...

in 2001, as a virtual/online conference in 2020 and 2021, and in

Italy Italy, officially the Italian Republic, is a country in Southern Europe, Southern and Western Europe, Western Europe. It consists of Italian Peninsula, a peninsula that extends into the Mediterranean Sea, with the Alps on its northern land b ...

in 2022; all other meetings in 1969–2023 have been held in the

. STOC was part of the Federated Computing Research Conference (FCRC) in 1993, 1996, 1999, 2003, 2007, 2011, 2015, 2019, and 2023.

Invited speakers

2004
: :
2005
:
2006
: :
2007
:
2008
: : :
2009
:

:
2011
: : : :
2013
: :
2014
:
video

video

2015

video
: : :
2016
: :
2017
: : :

Notes

References

*. *. *.

External links

*
STOC proceedings information
in

DBLP DBLP is a computer science bibliography website. Starting in 1993 at Universität Trier in Germany, it grew from a small collection of HTML files and became an organization hosting a database and logic programming bibliography site. Since Novem ...

.
STOC proceedings
in the ACM Digital Library.
Citation Statistics for FOCS/STOC/SODA
Piotr Indyk and Suresh Venkatasubramanian, July 2007. {{Authority control Theoretical computer science conferences Recurring events established in 1969 Association for Computing Machinery conferences