Symposium on Theory of Computing

El Simposio Anual de la ACM sobre Teoría de la Computación (nombre original en inglés: Annual ACM Symposium on Theory of Computing; STOC) es un congreso dedicado al campo de la ciencia computacional teórica, patrocinado por la Association for Computing Machinery SIGACT, una organización internacional originaria de los Estados Unidos. El simposio se ha organizado anualmente desde 1969, típicamente en mayo o junio. Su tasa de aceptación, promediada entre 1970 y 2012, es del 31 %, con una tasa del 29 % en 2012.[1]

Como escribe Fich (1996), el STOC y el FOCS (el Symposium on Foundations of Computer Science, su homólogo anual organizado por el Institute of Electrical and Electronics Engineers) se consideran las dos principales conferencias en ciencias de la computación teórica.[2] En términos generales, "son foros para algunos de los mejores trabajos en toda la teoría de la computación, que promueven la difusión de estos conocimientos entre los investigadores informáticos y ayudan a mantener unida a la comunidad”.Johnson (1984) incluye la asistencia regular a STOC y FOCS como uno de los hábitos característicos de los científicos informáticos teóricos.

Premios

El Premio Gödel para trabajos destacados en informática teórica se presenta alternativamente en el STOC y en el International Colloquium on Automata, Languages and Programming (ICALP); el Premio Knuth por contribuciones destacadas a los fundamentos de la informática se presenta alternativamente en el STOC y en el FOCS.

Desde 2003, el STOC ha presentado uno o más Premios al Mejor Artículo[3] para reconocer los trabajos de la más alta calidad en la conferencia. Además, el Premio Danny Lewin al Mejor Trabajo Estudiantil se otorga al autor(es) del mejor trabajo escrito por un estudiante en presentado al STOC.[4] El premio lleva el nombre de Daniel Lewin, un matemático y empresario estadounidense-israelí que cofundó la empresa de Internet Akamai y fue una de las primeras víctimas de los atentados del 11 de septiembre de 2001.[5]

Historia

El STOC se organizó por primera vez del 5 al 7 de mayo de 1969, en Marina del Rey, California, Estados Unidos. El presidente de la conferencia fue Patrick C. Fischer y el comité del programa estaba formado por Michael A. Harrison, Robert W. Floyd, Juris Hartmanis, Richard Karp, Albert R. Meyer y Jeffrey Ullman.[6]

Los primeros artículos seminales en el STOC incluyen trabajos de Cook (1971), que introdujo el concepto de NP-completo (véase también el teorema de Cook).

Ubicación

El simposio se organizó en Canadá en 1992, 1994, 2002 y 2008, y en Grecia en 2001; todas las demás reuniones entre 1969 y 2009 se han llevado a cabo en los Estados Unidos. Fue parte de la Federated Computing Research Conference (FCRC) en 1993, 1996, 1999, 2003, 2007 y 2011.

Oradores invitados
2004
Éva Tardos (2004), «Network games», Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04, pp. 341-342, ISBN 978-1581138528, doi:10.1145/1007352.1007356.
Avi Wigderson (2004), «Depth through breadth, or why should we attend talks in other areas?», Proceedings of the thirty-sixth annual ACM symposium on Theory of computing - STOC '04, p. 579, ISBN 978-1581138528, doi:10.1145/1007352.1007359.
2005
Lance Fortnow (2005), «Beyond NP: the work and legacy of Larry Stockmeyer», Proceedings of the thirty-seventh annual ACM symposium on Theory of computing - STOC '05, p. 120, ISBN 978-1581139600, doi:10.1145/1060590.1060609.
2006
Prabhakar Raghavan (2006), «The changing face of web search: algorithms, auctions and advertising», Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06, p. 129, ISBN 978-1595931344, doi:10.1145/1132516.1132535.
Russell Impagliazzo (2006), «Can every randomized algorithm be derandomized?», Proceedings of the thirty-eighth annual ACM symposium on Theory of computing - STOC '06, p. 373, ISBN 978-1595931344, doi:10.1145/1132516.1132571.
2007
Nancy Lynch (2007), «Distributed computing theory: algorithms, impossibility results, models, and proofs», Proceedings of the thirty-ninth annual ACM symposium on Theory of computing - STOC '07, p. 247, ISBN 9781595936318, doi:10.1145/1250790.1250826.
2008
Jennifer Rexford (2008), «Rethinking internet routing», Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08, pp. 55-56, ISBN 9781605580470, doi:10.1145/1374376.1374386.
David Haussler (2008), «Computing how we became human», Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08, pp. 639-640, ISBN 9781605580470, doi:10.1145/1374376.1374468.
Ryan O'Donnell (2008), «Some topics in analysis of boolean functions», Proceedings of the fortieth annual ACM symposium on Theory of computing - STOC 08, pp. 569-578, ISBN 9781605580470, doi:10.1145/1374376.1374458.
2009
Shafi Goldwasser (2009), «Athena lecture: Controlling Access to Programs?», Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09, pp. 167-168, ISBN 9781605585062, doi:10.1145/1536414.1536416.
2010
David S. Johnson (2010), "Approximation Algorithms in Theory and Practice" (Knuth Prize Lecture).
2011
Leslie G. Valiant (2011), "The Extent and Limitations of Mechanistic Explanations of Nature" (2010 ACM Turing Award Lecture).
Ravi Kannan (2011), "Algorithms: Recent Highlights and Challenges" (2011 Knuth Prize Lecture).
David A. Ferruci (2011), "IBM's Watson/DeepQA" (FCRC Plenary Talk).
Luiz Andre Barroso (2011), "Warehouse-Scale Computing: Entering the Teenage Decade" (FCRC Plenary Talk).
2013
Gary Miller (2013), Knuth Prize Lecture.
Prabhakar Raghavan (2013), Plenary talk.
2014
Thomas Rothvoss (2014), "The matching polytope has exponential extension complexity".
Shafi Goldwasser (2014), "The Cryptographic Lens" (Turing Award Lecture). vídeo
Silvio Micali (2014), "Proofs according to Silvio" (Turing Award Lecture). vídeo
2015
Michael Stonebraker (2015), Turing Award Lecture. vídeo
Andrew Yao (2015), FCRC Keynote Lecture.
László Babai (2015), Knuth Prize Lecture.
Olivier Temam (2015), FCRC Keynote Lecture.
2016
Santosh Vempala (2016), "The Interplay of Sampling and Optimization in High Dimension" (Invited Talk).
Timothy Chan (2016), "Computational Geometry, from Low to High Dimensions" (Invited Talk).
2017
Avi Wigderson (2017), "On the Nature and Future of ToC" (Keynote Talk).
Orna Kupferman (2017), "Examining classical graph-theory problems from the viewpoint of formal-verification methods" (Keynote Talk).
Oded Goldreich (2017), Knuth Prize Lecture.

Véase también
  • Conferencias sobre informática teórica.
  • Anexo:Conferencias de informática, que contiene otras conferencias académicas en informática.
  • Anexo:Premios de informática

Referencias
  1. «Proceedings of the 44th symposium on Theory of Computing». 2012. Consultado el 17 de septiembre de 2012.
  2. «Conference Ranks». Consultado el 30 de agosto de 2016.
  3. «STOC Conference Best Paper Awards». Consultado el 7 de abril de 2012.
  4. «Danny Lewin Best Student Paper Award». Archivado desde el original el 20 de junio de 2008.
  5. Leighton, Tom (2002). «Remarks made by Tom Leighton to commemorate the naming of the STOC Best Student Paper Award in honor of the late Daniel Lewin».
  6. Proc. STOC 1969. doi 10.1145/800169.

Bibliografía

Enlaces externos
Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.