Symposium sur la théorie de l'informatique - Symposium on Theory of Computing

Le Symposium annuel de l' ACM sur la théorie de l' informatique ( STOC ) est une conférence universitaire dans le domaine de l' informatique théorique . Le STOC est organisé chaque année depuis 1969, généralement en mai ou en juin ; la conférence est parrainée par le groupe d'intérêt spécial de l' Association for Computing Machinery SIGACT . Le taux d'acceptation du STOC, moyenné de 1970 à 2012, est de 31 %, avec un taux de 29 % en 2012.

Comme l' écrit Fich (1996) , STOC et son homologue annuel de l' IEEE FOCS (le Symposium sur les fondements de l'informatique ) sont considérés comme les deux meilleures conférences en informatique théorique, au sens large : ils « sont des forums pour certains des meilleurs travaux de théorie de informatique qui favorisent l'éventail des chercheurs en théorie de l'informatique et aident à garder la communauté unie. Johnson (1984) considère la fréquentation régulière du STOC et du FOCS comme l'une des caractéristiques déterminantes des informaticiens théoriques.

Récompenses

Le prix Gödel pour les articles exceptionnels en informatique théorique est présenté en alternance au STOC et au Colloque international sur les automates, les langages et la programmation (ICALP); le prix Knuth récompensant des contributions exceptionnelles aux fondements de l'informatique est décerné alternativement au STOC et au FOCS .

Depuis 2003, STOC a décerné un ou plusieurs prix du meilleur article pour récompenser les articles de la plus haute qualité lors de la conférence. De plus, le Danny Lewin Best Student Paper Award est décerné à l'auteur ou aux auteurs du meilleur article rédigé par des étudiants au STOC. Le prix est nommé en l'honneur de Daniel M. Lewin , un mathématicien et entrepreneur américano-israélien qui a cofondé la société Internet Akamai Technologies , et a été l'une des premières victimes des attentats du 11 septembre .

Histoire

STOC a été organisé pour la première fois du 5 au 7 mai 1969 à Marina del Rey , Californie , États-Unis . Le président de la conférence était Patrick C. Fischer et le comité du programme était composé de Michael A. Harrison , Robert W. Floyd , Juris Hartmanis , Richard M. Karp , Albert R. Meyer et Jeffrey D. Ullman .

Les premiers articles fondateurs de STOC incluent Cook (1971) , qui a introduit le concept de NP-complétude (voir aussi le théorème de Cook-Levin ).

Emplacement

STOC a été organisé au Canada en 1992, 1994, 2002 et 2008, et en Grèce en 2001; toutes les autres réunions de 1969 à 2009 ont eu lieu aux États-Unis . STOC a participé à la Federated Computing Research Conference (FCRC) en 1993, 1996, 1999, 2003, 2007 et 2011.

Conférenciers invités

2004
Éva Tardos (2004), "Jeux en réseau", Actes du trente-sixième symposium annuel de l'ACM sur la théorie de l'informatique - STOC '04 , pp. 341–342, doi : 10.1145/1007352.1007356 , ISBN 978-1581138528
Avi Wigderson (2004), "La profondeur à travers la largeur, ou pourquoi devrions-nous assister à des conférences dans d'autres domaines?", Actes du trente-sixième symposium annuel de l'ACM sur la théorie de l'informatique - STOC '04 , p. 579, doi : 10.1145/1007352.1007359 , ISBN 978-1581138528
2005
Lance Fortnow (2005), « Beyond NP : the work and legacy of Larry Stockmeyer », Actes du trente-septième symposium annuel de l'ACM sur la théorie de l'informatique - STOC '05 , p. 120, doi : 10.1145/1060590.1060609 , ISBN 978-1581139600
2006
Prabhakar Raghavan (2006), "Le visage changeant de la recherche sur le Web : algorithmes, enchères et publicité", Actes du trente-huitième symposium annuel de l'ACM sur la théorie de l'informatique - STOC '06 , p. 129, doi : 10.1145/1132516.1132535 , ISBN 978-1595931344
Russell Impagliazzo (2006), « Can every randomized algorithm be derandomized ? », Actes du trente-huitième symposium annuel de l'ACM sur la théorie de l'informatique - STOC '06 , p. 373, doi : 10.1145/1132516.1132571 , ISBN 978-1595931344
2007
Nancy Lynch (2007), "Distributed computing theory: algorithms, impossible results, models, and proofs", Actes du trente-neuvième symposium annuel de l'ACM sur la théorie de l'informatique - STOC '07 , p. 247, doi : 10.1145/1250790.1250826 , ISBN 9781595936318
2008
Jennifer Rexford (2008), "Rethinking internet routing", Actes du quarantième symposium annuel de l'ACM sur la théorie de l'informatique - STOC 08 , pp. 55-56, doi : 10.1145/1374376.1374386 , ISBN 9781605580470
David Haussler (2008), "Computer comment nous sommes devenus humains", Actes du quarantième symposium annuel de l'ACM sur la théorie de l'informatique - STOC 08 , pp. 639-640, doi : 10.1145/1374376.1374468 , ISBN 9781605580470
Ryan O'Donnell (2008), "Some topics in analysis of boolean functions", Actes du quarantième symposium annuel de l'ACM sur la théorie de l'informatique - STOC 08 , pp. 569-578, doi : 10.1145/1374376.1374458 , ISBN 9781605580470
2009
Shafi Goldwasser (2009), "Athena lecture: Controlling Access to Programs?", Actes du 41e symposium annuel de l'ACM sur le Symposium sur la théorie de l'informatique - STOC '09 , pp. 167-168, doi : 10.1145/1536414.1536416 , ISBN 9781605585062
2010
David S. Johnson (2010), « Algorithmes d'approximation en théorie et en pratique » (Conférence du prix Knuth)
2011
Leslie G. Valiant (2011), "The Extent and Limitations of Mechanistic Explanations of Nature" (Conférence ACM Turing Award 2010)
Ravi Kannan (2011), "Algorithms: Recent Highlights and Challenges" (conférence du prix Knuth 2011)
David A. Ferruci (2011), "IBM's Watson/DeepQA" (discussion en plénière du FCRC)
Luiz Andre Barroso (2011), "Warehouse-Scale Computing: Entering the Teenage Decade" (conférence plénière du FCRC)
2013
Gary Miller (2013), Conférence du Prix Knuth
Prabhakar Raghavan (2013), Conférence plénière
2014
Thomas Rothvoss (2014), "Le polytope correspondant a une complexité d'extension exponentielle"
Shafi Goldwasser (2014), "The Cryptographic Lens" (Conférence Turing Award) vidéo
Silvio Micali (2014), "Les preuves selon Silvio" (Conférence Turing Award) vidéo
2015
Michael Stonebraker (2015), Conférence Turing Award vidéo
Andrew Yao (2015), Conférence principale du CRFC
László Babai (2015), Conférence du Prix Knuth
Olivier Temam (2015), Conférence principale FCRC
2016
Santosh Vempala (2016), "L'interaction de l'échantillonnage et de l'optimisation en haute dimension" (conversation invitée)
Timothy Chan (2016), "Computational Geometry, from Low to High Dimensions" (Conversation invitée)
2017
Avi Wigderson (2017), "Sur la nature et l'avenir de la ToC" (discours principal)
Orna Kupferman (2017), "Examiner les problèmes classiques de la théorie des graphes du point de vue des méthodes de vérification formelle" (Keynote Talk)
Oded Goldreich (2017), Conférence du Prix Knuth

Voir également

Remarques

Les références

Liens externes