stringtranslate.com

Simposio sobre teoría de la computación

El Simposio Anual sobre Teoría de la Computación ( STOC ) de la ACM es una conferencia académica en el campo de la informática teórica . El STOC se organiza anualmente desde 1969, normalmente en mayo o junio; la conferencia está patrocinada por el grupo de interés especial SIGACT de la Association for Computing Machinery . La tasa de aceptación del STOC, en promedio desde 1970 hasta 2012, es del 31%, con una tasa del 29% en 2012. [1]

Como escribe Fich (1996), STOC y su homólogo anual del IEEE , FOCS (el Simposio sobre Fundamentos de la Ciencia de la Computación ), se consideran las dos conferencias más importantes en la ciencia de la computación teórica, [2] consideradas en términos generales: "son foros para algunos de los mejores trabajos en toda la teoría de la computación que promueven la amplitud entre los investigadores de la teoría de la computación y ayudan a mantener unida a la comunidad". Johnson (1984) incluye la asistencia regular a STOC y FOCS como una de varias características definitorias de los científicos informáticos teóricos.

Premios

El Premio Gödel para trabajos destacados en informática teórica se entrega alternativamente en STOC y en el Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP); el Premio Knuth para contribuciones destacadas a los fundamentos de la informática se entrega alternativamente en STOC y en FOCS .

Desde 2003, STOC ha otorgado uno o más premios al mejor artículo [3] para reconocer los artículos de la más alta calidad en la conferencia. Además, el premio Danny Lewin al mejor artículo estudiantil se otorga al autor o autores del mejor artículo escrito exclusivamente por estudiantes en STOC. [4] El premio recibe su nombre en honor a Daniel M. Lewin , un matemático y empresario estadounidense-israelí que cofundó la empresa de Internet Akamai Technologies y fue una de las primeras víctimas de los ataques del 11 de septiembre . [5]

Historia

La STOC se organizó por primera vez entre el 5 y el 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 estuvo formado por Michael A. Harrison , Robert W. Floyd , Juris Hartmanis , Richard M. Karp , Albert R. Meyer y Jeffrey D. Ullman . [6]

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

Ubicación

STOC se organizó en Canadá en 1992, 1994, 2002, 2008 y 2017, en Grecia en 2001, como conferencia virtual/en línea en 2020 y 2021, y en Italia en 2022; todas las demás reuniones entre 1969 y 2023 se han celebrado en los Estados Unidos . STOC formó parte de la Conferencia de Investigación en Computación Federada (FCRC) en 1993, 1996, 1999, 2003, 2007, 2011, 2015, 2019 y 2023.

Oradores invitados

2004
Éva Tardos (2004), "Juegos de red", Actas del trigésimo sexto simposio anual de la ACM sobre teoría de la computación - STOC '04 , pp. 341–342, doi :10.1145/1007352.1007356, ISBN 978-1581138528, Número de identificación del sujeto  18249534
Avi Wigderson (2004), "De la profundidad a la amplitud, o ¿por qué deberíamos asistir a charlas en otras áreas?", Actas del trigésimo sexto simposio anual de la ACM sobre teoría de la computación - STOC '04 , pág. 579, doi : 10.1145/1007352.1007359, ISBN 978-1581138528, Número de identificación del sujeto  27563516
2005
Lance Fortnow (2005), "Más allá de la NP: el trabajo y el legado de Larry Stockmeyer", Actas del trigésimo séptimo simposio anual de la ACM sobre teoría de la computación - STOC '05 , pág. 120, doi : 10.1145/1060590.1060609, ISBN 978-1581139600, Identificador único  16558679
2006
Prabhakar Raghavan (2006), "El rostro cambiante de la búsqueda web: algoritmos, subastas y publicidad", Actas del trigésimo octavo simposio anual de la ACM sobre teoría de la computación - STOC '06 , pág. 129, doi : 10.1145/1132516.1132535, ISBN 978-1595931344, S2CID19222958 ​
Russell Impagliazzo (2006), "¿Se puede desaleatorizar todo algoritmo aleatorio?", Actas del trigésimo octavo simposio anual de la ACM sobre teoría de la computación - STOC '06 , págs. 373-374, doi : 10.1145/1132516.1132571, ISBN 978-1595931344, Número de identificación del sujeto  22433370
2007
Nancy Lynch (2007), "Teoría de la computación distribuida: algoritmos, resultados de imposibilidad, modelos y pruebas", Actas del trigésimo noveno simposio anual de la ACM sobre teoría de la computación - STOC '07 , pág. 247, doi : 10.1145/1250790.1250826, ISBN 9781595936318, Número de identificación del sujeto  22140755
2008
Jennifer Rexford (2008), "Replanteando el enrutamiento de Internet", Actas del cuadragésimo simposio anual de la ACM sobre teoría de la computación - STOC 08 , págs. 55-56, doi : 10.1145/1374376.1374386, ISBN 9781605580470, Número de identificación del sujeto  10958242
David Haussler (2008), "La computación como forma de llegar a ser humanos", Actas del cuadragésimo simposio anual de la ACM sobre teoría de la computación - STOC 08 , págs. 639-640, doi : 10.1145/1374376.1374468, ISBN 9781605580470, Número de identificación del sujeto  30452365
Ryan O'Donnell (2008), "Algunos temas en el análisis de funciones booleanas", Actas del cuadragésimo simposio anual de la ACM sobre teoría de la computación - STOC 08 , págs. 569–578, doi :10.1145/1374376.1374458, ISBN 9781605580470, Número de identificación del sujeto  1241681
2009
Shafi Goldwasser (2009), "Conferencia Athena: ¿Cómo controlar el acceso a los programas?", Actas del 41.º simposio anual de la ACM sobre Simposio sobre teoría de la computación - STOC '09 , págs. 167-168, doi : 10.1145/1536414.1536416 , ISBN 9781605585062
2010
David S. Johnson (2010), "Algoritmos de aproximación en teoría y práctica" (Conferencia del Premio Knuth)
2011
Leslie G. Valiant (2011), "El alcance y las limitaciones de las explicaciones mecanicistas de la naturaleza" (Conferencia del Premio Turing de la ACM 2010)
Ravi Kannan (2011), "Algoritmos: aspectos destacados y desafíos recientes" (Conferencia del Premio Knuth 2011)
David A. Ferruci (2011), "Watson/DeepQA de IBM" (Charla plenaria del FCRC)
Luiz Andre Barroso (2011), "Computación a escala de almacén: entrando en la década de la adolescencia" (Charla plenaria del FCRC)
2013
Gary Miller (2013), conferencia sobre el premio Knuth
Prabhakar Raghavan (2013), charla plenaria
2014
Thomas Rothvoss (2014), "El politopo coincidente tiene una complejidad de extensión exponencial"
Shafi Goldwasser (2014), "La lente criptográfica" (Conferencia del Premio Turing)video
Silvio Micali (2014), "Las pruebas según Silvio" (Conferencia del Premio Turing)video
2015
Michael Stonebraker (2015), conferencia sobre el premio Turingvideo
Andrew Yao (2015), conferencia magistral del FCRC
László Babai (2015), Conferencia del Premio Knuth
Olivier Temam (2015), conferencia magistral del FCRC
2016
Santosh Vempala (2016), "La interacción entre muestreo y optimización en alta dimensión" (charla invitada)
Timothy Chan (2016), "Geometría computacional, desde dimensiones bajas a dimensiones altas" (Charla invitada)
2017
Avi Wigderson (2017), "Sobre la naturaleza y el futuro de la teoría del cambio" (discurso inaugural)
Orna Kupferman (2017), "Examen de problemas clásicos de teoría de grafos desde el punto de vista de métodos de verificación formal" (Charla magistral)
Oded Goldreich (2017), conferencia del Premio Knuth

Véase también

Notas

  1. ^ "Actas del 44º simposio sobre teoría de la computación". 2012 . Consultado el 17 de septiembre de 2012 .
  2. ^ "Ranking de conferencias" . Consultado el 30 de agosto de 2016 .
  3. ^ "Premios al mejor artículo de la conferencia STOC" . Consultado el 7 de abril de 2012 .
  4. ^ "Premio Danny Lewin al mejor trabajo estudiantil". Archivado desde el original el 20 de junio de 2008.
  5. ^ Leighton, Tom (2002). "Comentarios hechos por Tom Leighton para conmemorar la designación del premio STOC al mejor artículo estudiantil en honor del difunto Daniel Lewin".
  6. ^ Procedimiento. STOC 1969. doi : 10.1145/800169.

Referencias

Enlaces externos