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

History

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

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

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

Richard M. Karp Richard Manning Karp (born January 3, 1935) is an American computer scientist and computational theorist at the University of California, Berkeley. He is most notable for his research in the theory of algorithms, for which he received a Turing ...

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

, 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 (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 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 (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.
STOC proceedings
in the ACM Digital Library.
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 Suresh Venkatasubramanian is an Indian computer scientist and professor at Brown University. In 2021, Prof. Venkatasubramanian was appointed to the White House Office of Science and Technology Policy, advising on matters relating to fairness and bi ...

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