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[editar]
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[editar]
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[editar]
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[editar]
- 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[editar]
- 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[editar]
- ↑ «Proceedings of the 44th symposium on Theory of Computing». 2012. Consultado el 17 de septiembre de 2012.
- ↑ «Conference Ranks». Consultado el 30 de agosto de 2016.
- ↑ «STOC Conference Best Paper Awards». Consultado el 7 de abril de 2012.
- ↑ «Danny Lewin Best Student Paper Award». Archivado desde el original el 20 de junio de 2008.
- ↑ 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».
- ↑ Proc. STOC 1969. doi 10.1145/800169.
Bibliografía[editar]
- Cook, Stephen (1971), «The complexity of theorem proving procedures», Proc. STOC 1971, pp. 151-158, doi:10.1145/800157.805047..
- Fich, Faith (1996), «Infrastructure issues related to theory of computing research», ACM Computing Surveys 28 (4es): 217-es, doi:10.1145/242224.242502..
- Johnson, D. S. (1984), «The genealogy of theoretical computer science: a preliminary report», ACM SIGACT News 16 (2): 36-49, doi:10.1145/1008959.1008960..
Enlaces externos[editar]
- Web oficial
- Información de procedimientos STOC en Digital Bibliography & Library Project.
- actas STOC en el Association for Computing Machinery.
- Citation Statistics for FOCS/STOC/SODA Archivado el 22 de abril de 2016 en Wayback Machine., Piotr Indyk y Suresh Venkatasubramanian, julio de 2007.
Datos: Q7661893