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.

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

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

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

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

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 (en), « 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

(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).

(en) « Proceedings of the 44th symposium on Theory of Computing », 2012 (consulté le 17 septembre 2012)
« Proceedings of the 48th symposium on Theory of Computing - Frontmatter », 2016.
Faith Fich, « Infrastructure issues related to theory of computing research », ACM Computing Surveys, vol. 28, n^o 4es,‎ décembre 1996, article n^o 217 (DOI 10.1145/242224.242502).
(en) « Conference Ranks » (consulté le 30 août 2016).
« STOC Conference Best Paper Awards » (consulté le 7 avril 2012).
« Danny Lewin Best Student Paper Award ».
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.
Proc. STOC 1969.

Articles connexes

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

Liens externes

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

Portail de l'informatique théorique

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[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, n^o 4es,‎ décembre 1996, article n^o 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.