Symposium on Theory of Computing

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{{cite web | url=http://jeffhuang.com/best_paper_awards.html#stoc | title=STOC Conference Best Paper Awards | access-date=2012-04-07 }} 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.{{cite web

|url = http://sigact.acm.org/prizes/student/

|title = Danny Lewin Best Student Paper Award

|url-status = dead

|archive-url = https://web.archive.org/web/20080620010241/http://sigact.acm.org/prizes/student/

|archive-date = 2008-06-20

}} The award is named in honor of Daniel M. Lewin, 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.{{cite web

| url=http://www.egr.unlv.edu/~bein/SIGACT/lewin.html

| first=Tom | last=Leighton

| year=2002

| title=Remarks made by Tom Leighton to commemorate the naming of the STOC Best Student Paper Award in honor of the late Daniel Lewin

}}

STOC was first organised on 5–7 May 1969, in Marina del Rey, California, United States. 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. {{doi|10.1145/800169}}.

Early seminal papers in STOC include {{harvtxt|Cook|1971}}, which introduced the concept of NP-completeness (see also Cook–Levin theorem).

STOC was organised in Canada in 1992, 1994, 2002, 2008, and 2017 in Greece in 2001, as a virtual/online conference in 2020 and 2021, and in Italy in 2022; all other meetings in 1969–2023 have been held in the United States. STOC was part of the Federated Computing Research Conference (FCRC) in 1993, 1996, 1999, 2003, 2007, 2011, 2015, 2019, and 2023.

;[https://dblp.org/db/conf/stoc/stoc2004 2004]

:{{citation

| doi=10.1145/1007352.1007356

| author=Éva Tardos

| title=Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04

| chapter=Network games

| year=2004

| pages=341–342

| isbn=978-1581138528

| s2cid=18249534

| author-link=Éva Tardos

}}

:{{citation

| doi=10.1145/1007352.1007359

| author=Avi Wigderson

| title=Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04

| chapter=Depth through breadth, or why should we attend talks in other areas?

| year=2004

| pages=579

| isbn=978-1581138528

| s2cid=27563516

| author-link=Avi Wigderson

}}

;[https://dblp.org/db/conf/stoc/stoc2005 2005]

:{{citation

| doi=10.1145/1060590.1060609

| author=Lance Fortnow

| title=Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05

| chapter=Beyond NP: the work and legacy of Larry Stockmeyer

| year=2005

| pages=120

| isbn=978-1581139600

| s2cid=16558679

| author-link=Lance Fortnow

}}

;[https://dblp.org/db/conf/stoc/stoc2006 2006]

:{{citation

| doi=10.1145/1132516.1132535

| author=Prabhakar Raghavan

| title=Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06

| chapter=The changing face of web search: algorithms, auctions and advertising

| year=2006

| pages=129

| isbn=978-1595931344

| s2cid=19222958

| author-link=Prabhakar Raghavan

}}

:{{citation

| doi=10.1145/1132516.1132571

| author=Russell Impagliazzo

| title=Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06

| chapter=Can every randomized algorithm be derandomized?

| year=2006

| pages=373–374

| isbn=978-1595931344

| s2cid=22433370

| author-link=Russell Impagliazzo

}}

;[https://dblp.org/db/conf/stoc/stoc2007 2007]

:{{citation

| doi=10.1145/1250790.1250826

| author=Nancy Lynch

| title=Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07

| chapter=Distributed computing theory: algorithms, impossibility results, models, and proofs

| year=2007

| pages=247

| isbn=9781595936318

| s2cid=22140755

| author-link=Nancy Lynch

}}

;[https://dblp.org/db/conf/stoc/stoc2008 2008]

:{{citation

| doi=10.1145/1374376.1374386

| author=Jennifer Rexford

| title=Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08

| chapter=Rethinking internet routing

| year=2008

| pages=55–56

| isbn=9781605580470

| s2cid=10958242

| author-link=Jennifer Rexford

}}

:{{citation

| doi=10.1145/1374376.1374468

| author=David Haussler

| title=Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08

| chapter=Computing how we became human

| year=2008

| pages=639–640

| isbn=9781605580470

| s2cid=30452365

| author-link=David Haussler

}}

:{{citation

| doi=10.1145/1374376.1374458

| author=Ryan O'Donnell

| title=Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08

| chapter=Some topics in analysis of boolean functions

| year=2008

| pages=569–578

| isbn=9781605580470

| s2cid=1241681

| author-link=Ryan O'Donnell (computer scientist)

}}

;[https://dblp.org/db/conf/stoc/stoc2009 2009]

:{{citation

| doi=10.1145/1536414.1536416

| author=Shafi Goldwasser

| title=Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09

| chapter=Athena lecture: Controlling Access to Programs?

| year=2009

| pages=167–168

| isbn=9781605585062

| author-link=Shafi Goldwasser

| doi-access=free

}}

;[http://acm-stoc.org/stoc2010/program.htm 2010]

:{{citation

| author=David S. Johnson

| title="Approximation Algorithms in Theory and Practice" (Knuth Prize Lecture)

| year=2010

| author-link=David S. Johnson

}}

;[http://acm-stoc.org/stoc2011/ 2011]

:{{citation

| author=Leslie G. Valiant

| title="The Extent and Limitations of Mechanistic Explanations of Nature" (2010 ACM Turing Award Lecture)

| year=2011

| author-link=Leslie G. Valiant

}}

:{{citation

| author=Ravi Kannan

| title="Algorithms: Recent Highlights and Challenges" (2011 Knuth Prize Lecture)

| year=2011

| author-link=Ravi Kannan

}}

:{{citation

| author=David A. Ferruci

| title="IBM's Watson/DeepQA" (FCRC Plenary Talk)

| year=2011

}}

:{{citation

| author=Luiz Andre Barroso

| title="Warehouse-Scale Computing: Entering the Teenage Decade" (FCRC Plenary Talk)

| year=2011

}}

;[http://theory.stanford.edu/stoc2013/ 2013]

:{{citation

| author=Gary Miller

| title=Knuth Prize Lecture

| year=2013

| author-link=Gary Miller (computer scientist)

}}

:{{citation

| author=Prabhakar Raghavan

| title = Plenary talk

| year=2013

| author-link=Prabhakar Raghavan

}}

;[http://www.columbia.edu/~cs2035/stoc/stoc2014/ 2014]

:{{citation

| author=Thomas Rothvoss

| title="The matching polytope has exponential extension complexity"

| year=2014

| author-link=Thomas Rothvoss

}}

:{{citation

| author=Shafi Goldwasser

| title= "The Cryptographic Lens" (Turing Award Lecture)

| year=2014

| author-link=Shafi Goldwasser

}} [http://amturing.acm.org/vp/goldwasser_8627889.cfm video]

:{{citation

| author=Silvio Micali

| title= "Proofs according to Silvio" (Turing Award Lecture)

| year=2014

| author-link=Silvio Micali

}} [https://amturing.acm.org/vp/micali_9954407.cfm video]

;[http://acm-stoc.org/stoc2015/ 2015]

:{{citation

| author=Michael Stonebraker

| title=Turing Award Lecture

| year=2015

| author-link=Michael Stonebraker

}} [https://amturing.acm.org/vp/stonebraker_1172121.cfm video]

:{{citation

| author=Andrew Yao

| title= FCRC Keynote Lecture

| year=2015

| author-link=Andrew Yao

}}

:{{citation

| author=László Babai

| title= Knuth Prize Lecture

| year=2015

| author-link=László Babai

}}

:{{citation

| author=Olivier Temam

| title = FCRC Keynote Lecture

| year=2015

}}

;[http://acm-stoc.org/stoc2016/ 2016]

:{{citation

| author=Santosh Vempala

| title="The Interplay of Sampling and Optimization in High Dimension" (Invited Talk)

| year=2016

| author-link=Santosh Vempala

}}

:{{citation

| author=Timothy Chan

| title="Computational Geometry, from Low to High Dimensions" (Invited Talk)

| year=2016

| author-link=Timothy Chan

}}

;[http://acm-stoc.org/stoc2017/ 2017]

:{{citation

| author=Avi Wigderson

| title="On the Nature and Future of ToC" (Keynote Talk)

| year=2017

| author-link=Avi Wigderson

}}

:{{citation

| author=Orna Kupferman

| title="Examining classical graph-theory problems from the viewpoint of formal-verification methods" (Keynote Talk)

| year=2017

| author-link=Orna Kupferman

}}

:{{citation

| author=Oded Goldreich

| title=Knuth Prize Lecture

| year=2017

| author-link=Oded Goldreich

}}

• Conferences in theoretical computer science.
• List of computer science conferences contains other academic conferences in computer science.
• List of computer science awards

{{Reflist}}

• {{citation

| last=Cook | first=Stephen | author-link=Stephen Cook

| year=1971

| chapter=The complexity of theorem proving procedures

| title=Proc. STOC 1971

| pages=151–158

| doi=10.1145/800157.805047 | s2cid=7573663 | chapter-url=http://www.inf.unibz.it/~calvanese/teaching/13-14-tc/material/cook-1971-NP-completeness-of-SAT.pdf

| doi-access=free

}}.

• {{citation

| last = Fich | first = Faith | author-link = Faith Ellen

| title = Infrastructure issues related to theory of computing research

| journal = ACM Computing Surveys

| volume = 28 | issue = 4es | doi = 10.1145/242224.242502

| year = 1996

| pages = 217–es| s2cid = 195706843 }}.

• {{citation

| last = Johnson | first = D. S. | author-link = David S. Johnson

| title = The genealogy of theoretical computer science: a preliminary report

| journal = ACM SIGACT News

| year = 1984 | volume = 16 | issue = 2 | pages = 36–49 | doi = 10.1145/1008959.1008960| s2cid = 26789249 }}.

• {{Official website}}
• [https://dblp.org/streams/conf/stoc STOC proceedings information] in DBLP.
• [https://dl.acm.org/conference/stoc/proceedings STOC proceedings] in the ACM Digital Library.
• [http://www.cs.utah.edu/~suresh/citations/ Citation Statistics for FOCS/STOC/SODA], Piotr Indyk and Suresh Venkatasubramanian, July 2007.

{{Association for Computing Machinery}}

{{Authority control}}

Category:Theoretical computer science conferences

Category:Recurring events established in 1969

Category:Association for Computing Machinery conferences