Symposium on Theory of Computing

Ne doit pas être confondu avec Stoc.

Symposium on Theory of Computing (STOC)

Type  | Conférence académique
Création  | 1969
Localisation  | villes variées, en Amérique du Nord principalement
Date  | annuelle
Site web  | http://sigact.acm.org/stoc.html
modifier

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%[1] ; en 2016, 92 articles sur 370 proposés ont été acceptés [2].

Déjà en 1996, Faith Ellen Fich[3] 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[4].

## Prix

[modifier | modifier le code]

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[5] 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[6]; cette récompense porte le nom de Daniel M. Lewin[7]. Le FOCS décerne également un tel prix qui porte le nom de Machtey Award (en).

## Histoire

[modifier | modifier le code]

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[8].

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

[modifier | modifier le code]

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)

## Notes et références

[modifier | modifier le code]

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Symposium on Theory of Computing » (voir la liste des auteurs).

1. ↑ (en) « Proceedings of the 44th symposium on Theory of Computing », 2012 (consulté le 17 septembre 2012)
2. ↑ « Proceedings of the 48th symposium on Theory of Computing - Frontmatter », 2016.
3. ↑ Faith Fich, « Infrastructure issues related to theory of computing research », ACM Computing Surveys, vol. 28, no 4es,‎ décembre 1996, article no 217 (DOI 10.1145/242224.242502).
4. ↑ (en) « Conference Ranks » (consulté le 30 août 2016).
5. ↑ « STOC Conference Best Paper Awards » (consulté le 7 avril 2012).
6. ↑ « Danny Lewin Best Student Paper Award ».
7. ↑ Tom Leighton, « Remarks made by Tom Leighton to commemorate the naming of the STOC Best Student Paper Award in honor of the late Daniel Lewin », 2002.
8. ↑ Proc. STOC 1969.

## Articles connexes

[modifier | modifier le code]

* Liste des principales conférences d'informatique théorique
* List of computer science conferences (en)

## Liens externes

[modifier | modifier le code]

* page officielle STOC.
* Proceedings des STOC sur DBLP.
* STOC proceedings sur ACM digital library.

* Portail de l'informatique théorique
* Portail de la recherche scientifique

*[(en)]: Langue : anglais
*[vol.]: volume
*[no]: numéro