Symposium on Theory of Computing
# 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.

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

## 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.

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 .
