# Symposium on Theory of Computing

La conférence Annual ACM Symposium on Theory of Computing (abrégé en STOC) est une conférence scientifique dans le domaine de l’informatique théorique. STOC a lieu chaque année depuis 1969, habituellement en mai ou juin ; la conférence est organisé par le Special Interest Group on Algorithms and Computation Theory (SIGACT) de l'Association for Computing Machinery.
Le taux d'acceptation des articles proposés au STOC est, en moyenne entre 1970 et 2012, de 31% ; en 2016, 92 articles sur 370 proposés ont été acceptés .
Déjà en 1996, Faith Ellen Fich note que la conférence STOC et sa contrepartie, la conférence Symposium on Foundations of Computer Science (FOCS) de l'IEEE sont considérées comme les deux conférences les plus importantes en informatique théorique. En 2014, le classement de Microsoft confirme cette prédominance.

## Prix

Le prix Gödel pour des contributions exceptionnelles à l'informatique théorique est remis en alternance à STOC et à l'International Colloquium on Automata, Languages and Programming (ICALP) ; le prix Donald E. Knuth pour des contributions exceptionnelles à l'informatique théorique est remis en alternance à STOC et à FOCS.
Depuis 2003, STOC décerne un ou plusieurs prix pour le meilleur article de la conférence. De plus, le « Danny Lewin Best Student Paper Award » est décerné aux auteurs du meilleur article présenté par des étudiants; cette récompense porte le nom de Daniel M. Lewin. Le FOCS décerne également un tel prix qui porte le nom de Machtey Award (en).

## Histoire

Le premier STOC a eu lieu du 5 au 7 mai 1969, à Marina Del Rey, en Californie. Le président était Patrick C. Fischer, et le comité de programme était composé de Michael A. Harrison, Robert W. Floyd, Juris Hartmanis, Richard M. Karp, Albert R. Meyer, et Jeffrey D. Ullman.
Les conférences ont lieu habituellement aux États-Unis, à quelques exceptions près : STOC a eu lieu au Canada en 1992, 1994, 2002, et 2008, et en Grèce en 2001.

## Orateurs invités
### 2004

    (en) Éva Tardos, « Network games », STOC,‎ 2004 (DOI 10.1145/1007352.1007356)
    (en) Avi Wigderson, « Depth through breadth, or why should we attend talks in other areas? », STOC,‎ 2004 (DOI 10.1145/1007352.1007359)

### 2005

    Lance Fortnow (en), « Beyond NP: the work and legacy of Larry Stockmeyer », STOC,‎ 2005 (DOI 10.1145/1060590.1060609)

### 2006

    Prabhakar Raghavan, « The changing face of web search: algorithms, auctions and advertising », STOC,‎ 2006 (DOI 10.1145/1132516.1132535)
    Russell Impagliazzo, « Can every randomized algorithm be derandomized? », STOC,‎ 2006 (DOI 10.1145/1132516.1132571)

### 2007

    Nancy Lynch, « Distributed computing theory: algorithms, impossibility results, models, and proofs », STOC,‎ 2007 (DOI 10.1145/1250790.1250826)

### 2008

    Jennifer Rexford, « Rethinking internet routing », STOC,‎ 2008 (DOI 10.1145/1374376.1374386)
    David Haussler, « Computing how we became human », STOC,‎ 2008 (DOI 10.1145/1374376.1374468)
    Ryan O'Donnell (en), « Some topics in analysis of boolean functions », STOC,‎ 2008 (DOI 10.1145/1374376.1374458)

### 2009

    Shafi Goldwasser, « Athena lecture: Controlling Access to Programs? », STOC,‎ 2009 (DOI 10.1145/1536414.1536416)