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
(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 US ...
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 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 establis ...
,
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 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
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 ...
. 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:
videovideo2015video:
:
:
2016:
:
2017:
:
:
See also
*
Conferences
A conference is a meeting of two or more experts to discuss and exchange opinions or new information about a particular topic.
Conferences can be used as a form of group decision-making, although discussion, not always decisions, are the main pu ...
in theoretical computer science.
*
List of computer science conferences
This is a list of academic conferences in computer science. Only conferences with separate articles are included; within each field, the conferences are listed alphabetically by their short names.
General
* FCRC – Federated Computing Research C ...
contains other academic conferences in computer science.
*
List of computer science awards
This list of computer science awards is an index to articles on notable awards related to computer science. It includes lists of awards by the Association for Computing Machinery, the Institute of Electrical and Electronics Engineers, other comput ...
Notes
References
*.
*.
*.
External links
*
STOC proceedings informationin
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 proceedingsin 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
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