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

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

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

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

. 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 Daniel is a masculine given name and a surname of Hebrew origin. It means "God is my judge"Hanks, Hardcastle and Hodges, ''Oxford Dictionary of First Names'', Oxford University Press, 2nd edition, , p. 68. (cf. Gabriel—"God is my strength"), ...

, 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 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 commerc ...

History

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

California California is a state in the Western United States, located along the Pacific Coast. With nearly 39.2million residents across a total area of approximately , it is the most populous U.S. state and the 3rd largest by area. It is also the ...

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 U.S. state, states, a Washington, D.C., federal district, five ma ...

. 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, 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 tryin ...

(see also Cook–Levin theorem).

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

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

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

. STOC was part of the Federated Computing Research Conference (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 No ...

.
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