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 event for researchers (not necessarily academics) to present and discuss their scholarly work. Together with academic or scientific journals an ...

in the field of

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

. 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 member ...

special interest group

SIGACT 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. Publi ...

. 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 a 501(c)(3) professional association for electronic engineering and electrical engineering (and associated disciplines) with its corporate office in New York City and its operation ...

counterpart FOCS (the

Symposium on Foundations of Computer Science 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. As writes, FOCS and its annual Association for Computing ...

) 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 International Colloquium on Automata, Languages, and Programming is an academic conference organized annually by the European Association for Theoretical Computer Science and held in different locations around Europe. Like most theoret ...

(ICALP); the

Knuth Prize 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. History The Knuth Prize has been awarded since 1996 and includes an award of U ...

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-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 content delivery networkJ. Dilley, B. Maggs, J. Parikh, H. Prokop, R. Sitaraman, and B. Weihl. (CDN), cybersecurity, and cloud service company, providing web and Internet security services. Akamai's Inte ...

, and was one of the first victims of the

September 11 attacks The September 11 attacks, commonly known as 9/11, were four coordinated suicide terrorist attacks carried out by al-Qaeda against the United States on Tuesday, September 11, 2001. That morning, nineteen terrorists hijacked four commercia ...

History

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

Marina del Rey Marina del Rey (Spanish language, Spanish for "Marina of the King") is an unincorporated area, unincorporated seaside community in Los Angeles County, California, with an eponymous harbor that is a major boating and water recreation destination ...

California California is a U.S. state, state in the Western United States, located along the West Coast of the United States, Pacific Coast. With nearly 39.2million residents across a total area of approximately , it is the List of states and territori ...

United States The United States of America (U.S.A. or USA), commonly known as the United States (U.S. or US) or America, is a country primarily located in North America. It consists of 50 states, a federal district, five major unincorporated territorie ...

. The conference chairman was

Patrick C. Fischer Patrick Carl Fischer (December 3, 1935 – August 26, 2011) was an American computer scientist, a noted researcher in computational complexity theory and database theory, and a target of the Unabomber..Michael A. Harrison Michael A. Harrison is a computer scientist, in particular a pioneer in the area of formal languages. Biography Michael A. Harrison (born in Philadelphia, Pennsylvania, U.S.) studied electrical engineering and computing for BS and MS at the Case ...

Robert W. Floyd Robert W Floyd (June 8, 1936 – September 25, 2001) was a computer scientist. His contributions include the design of the Floyd–Warshall algorithm (independently of Stephen Warshall), which efficiently finds all shortest paths in a graph and ...

Juris Hartmanis Juris Hartmanis (July 5, 1928 – July 29, 2022) was a Latvian-born American computer scientist and computational theorist who, with Richard E. Stearns, received the 1993 ACM Turing Award "in recognition of their seminal paper which establis ...

, Richard M. Karp,

Albert R. Meyer Albert Ronald da Silva Meyer (born 1941) is Hitachi America Professor emeritus of computer science at Massachusetts Institute of Technology (MIT). Biography Meyer received his PhD from Harvard University in 1972 in applied mathematics, under t ...

, and

Jeffrey D. Ullman Jeffrey David Ullman (born November 22, 1942) is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers (various editions are popularly known as the ...

.Proc. STOC 1969. . Early seminal papers in STOC include , which introduced the concept of

NP-completeness In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

(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-complete. That is, it is in NP, and any problem in NP can be reduced in polynomial time by a determi ...

Location

STOC was organised in

Canada Canada is a country in North America. Its ten provinces and three territories extend from the Atlantic Ocean to the Pacific Ocean and northward into the Arctic Ocean, covering over , making it the world's second-largest country by tot ...

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

Greece Greece,, or , romanized: ', officially the Hellenic Republic, is a country in Southeast Europe. It is situated on the southern tip of the Balkans, and is located at the crossroads of Europe, Asia, and Africa. Greece shares land borders with ...

in 2001; all other meetings in 1969–2009 have been held in the

. STOC was part of the

Federated Computing Research Conference The Federated Computing Research Conference, FCRC, is an event that brings together several academic conferences, workshops, and plenary talks in the field of computer science. FCRC has been organised in 1993, 1996, 1999, 2003, 2007, 2011, 2015 and ...

(FCRC) in 1993, 1996, 1999, 2003, 2007, and 2011.

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 Nove ...

.
STOC proceedings
in the

ACM Digital Library 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 member ...

.
Citation Statistics for FOCS/STOC/SODA

Piotr Indyk Piotr Indyk is Thomas D. and Virginia W. Cabot Professor in the Theory of Computation Group at the Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology. Academic biography Indyk received the Magister (MA) ...

and Suresh Venkatasubramanian, July 2007. {{Authority control Theoretical computer science conferences Recurring events established in 1969 Association for Computing Machinery conferences