stringtranslate.com

Simposio sobre Teoría de la Computación

El Simposio Anual ACM sobre Teoría de la Computación ( STOC ) es una conferencia académica en el campo de la informática teórica . 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 Asociación de Maquinaria de Computación . La tasa de aceptación de STOC, promediada entre 1970 y 2012, es del 31%, con una tasa del 29% en 2012. [1]

Como escribe Fich (1996), STOC y su contraparte anual IEEE FOCS (el Simposio sobre Fundamentos de Ciencias de la Computación ) se consideran las dos conferencias más importantes en ciencias 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 las varias características que definen a los científicos informáticos teóricos.

Premios

El Premio Gödel a 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 por sus destacadas contribuciones a los fundamentos de la informática se entrega alternativamente en STOC y FOCS .

Desde 2003, STOC ha presentado 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 a los autores del mejor artículo escrito exclusivamente por estudiantes en STOC. [4] El premio lleva el nombre de 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

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 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 fundamentales en STOC incluyen a Cook (1971), que introdujo el concepto de completitud NP (ver 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 celebraron en los Estados Unidos . STOC formó parte de la Conferencia Federada de Investigación en Computación (FCRC) en 1993, 1996, 1999, 2003, 2007, 2011, 2015, 2019 y 2023.

Oradores invitados

2004
Éva Tardos (2004), "Juegos en red", Actas del trigésimo sexto simposio anual ACM sobre teoría de la informática - STOC '04 , págs. 341–342, doi :10.1145/1007352.1007356, ISBN 978-1581138528, S2CID  18249534
Avi Wigderson (2004), "Profundidad a través de la amplitud, o ¿por qué deberíamos asistir a charlas en otras áreas?", Actas del trigésimo sexto simposio anual ACM sobre teoría de la informática - STOC '04 , p. 579, doi :10.1145/1007352.1007359, ISBN 978-1581138528, S2CID  27563516
2005
Lance Fortnow (2005), "Más allá de NP: el trabajo y el legado de Larry Stockmeyer", Actas del trigésimo séptimo simposio anual de ACM sobre teoría de la computación - STOC '05 , p. 120, doi :10.1145/1060590.1060609, ISBN 978-1581139600, S2CID  16558679
2006
Prabhakar Raghavan (2006), "La cara cambiante de la búsqueda web: algoritmos, subastas y publicidad", Actas del trigésimo octavo simposio anual ACM sobre teoría de la informática - STOC '06 , p. 129, doi :10.1145/1132516.1132535, ISBN 978-1595931344, S2CID  19222958
Russell Impagliazzo (2006), "¿Se puede desrandomizar cada algoritmo aleatorio?", Actas del trigésimo octavo simposio anual ACM sobre teoría de la computación - STOC '06 , págs. 373–374, doi :10.1145/1132516.1132571, ISBN 978-1595931344, S2CID  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 ACM sobre teoría de la computación - STOC '07 , p. 247, doi :10.1145/1250790.1250826, ISBN 9781595936318, S2CID  22140755
2008
Jennifer Rexford (2008), "Repensar el enrutamiento de Internet", Actas del cuadragésimo simposio anual de ACM sobre teoría de la informática - STOC 08 , págs. 55–56, doi :10.1145/1374376.1374386, ISBN 9781605580470, S2CID  10958242
David Haussler (2008), "Computar cómo nos convertimos en humanos", Actas del cuadragésimo simposio anual de ACM sobre teoría de la informática - STOC 08 , págs. 639–640, doi :10.1145/1374376.1374468, ISBN 9781605580470, S2CID  30452365
Ryan O'Donnell (2008), "Algunos temas en el análisis de funciones booleanas", Actas del cuadragésimo simposio anual de ACM sobre teoría de la computación - STOC 08 , págs. 569–578, doi :10.1145/1374376.1374458, ISBN 9781605580470, S2CID  1241681
2009
Shafi Goldwasser (2009), "Conferencia de Athena: ¿Control del acceso a los programas?", Actas del 41.º simposio anual de ACM sobre teoría de la informática - 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 ACM Turing 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 de la FCRC)
Luiz Andre Barroso (2011), "Computación a escala de almacén: entrada a la década de la adolescencia" (charla plenaria de la FCRC)
2013
Gary Miller (2013), Conferencia del 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 Premio Turing)video
2015
Michael Stonebraker (2015), Conferencia del Premio Turingvideo
Andrew Yao (2015), Conferencia magistral de la FCRC
László Babai (2015), Conferencia del Premio Knuth
Olivier Temam (2015), Conferencia magistral de la FCRC
2016
Santosh Vempala (2016), "La interacción del muestreo y la optimización en alta dimensión" (charla invitada)
Timothy Chan (2016), "Geometría computacional, de dimensiones bajas a altas" (charla invitada)
2017
Avi Wigderson (2017), "Sobre la naturaleza y el futuro de la ToC" (charla magistral)
Orna Kupferman (2017), "Examen de los problemas de la teoría de grafos clásica desde el punto de vista de los métodos de verificación formal" (charla magistral)
Oded Goldreich (2017), Conferencia del Premio Knuth

Ver también

Notas

  1. ^ "Actas del 44º simposio sobre Teoría de la Computación". 2012 . Consultado el 17 de septiembre de 2012 .
  2. ^ "Rangos 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 artículo estudiantil". Archivado desde el original el 20 de junio de 2008.
  5. ^ Leighton, Tom (2002). "Palabras hechas por Tom Leighton para conmemorar la concesión del premio STOC al mejor artículo estudiantil en honor al fallecido Daniel Lewin".
  6. ^ Procedimiento. STOC 1969. doi : 10.1145/800169.

Referencias

enlaces externos