Simposio de Teoría de la Computación - Symposium on Theory of Computing

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 ha organizado anualmente desde 1969, normalmente en mayo o junio; la conferencia está patrocinada por el grupo de interés especial de la Asociación de Maquinaria de Computación SIGACT . La tasa de aceptación de STOC, promediada de 1970 a 2012, es del 31%, con una tasa del 29% en 2012.

Como escribe Fich (1996) , STOC y su contraparte anual de IEEE FOCS (el Simposio sobre Fundamentos de la Ciencia de la Computación ) son consideradas las dos mejores conferencias en ciencias de la computación teóricas, consideradas ampliamente: son foros para algunos de los mejores trabajos a lo largo de la teoría de la computación. informática que promueve la amplitud entre los investigadores de la teoría de la informática y ayuda 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 presenta alternativamente en STOC y en el Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP); el Premio Knuth por sus contribuciones destacadas a los fundamentos de la informática se presenta alternativamente en STOC y en FOCS .

Desde 2003, STOC ha presentado uno o más premios al mejor artículo para reconocer los artículos de la más alta calidad en la conferencia. Además, el premio Danny Lewin Best Student Paper Award se otorga al autor (es) del mejor artículo escrito por estudiantes en STOC. 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 .

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 integrado por Michael A. Harrison , Robert W. Floyd , Juris Hartmanis , Richard M. Karp , Albert R. Meyer y Jeffrey D. Ullman .

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

Localización

STOC se organizó en Canadá en 1992, 1994, 2002 y 2008, y en Grecia en 2001; todas las demás reuniones de 1969–2009 se han celebrado en los Estados Unidos . STOC fue parte de la Conferencia de Investigación en Computación Federada (FCRC) en 1993, 1996, 1999, 2003, 2007 y 2011.

Ponentes invitados

2004
Éva Tardos (2004), "Juegos en red", Actas del trigésimo sexto simposio anual de ACM sobre teoría de la computación - STOC '04 , págs. 341–342, doi : 10.1145 / 1007352.1007356 , ISBN 978-1581138528
Avi Wigderson (2004), "De profundidad a amplitud, o ¿por qué deberíamos asistir a charlas en otras áreas?", Actas del trigésimo sexto simposio anual de ACM sobre teoría de la computación - STOC '04 , p. 579, doi : 10.1145 / 1007352.1007359 , ISBN 978-1581138528
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
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 computación - STOC '06 , p. 129, doi : 10.1145 / 1132516.1132535 , ISBN 978-1595931344
Russell Impagliazzo (2006), "¿Se puede desaleatorizar cada algoritmo aleatorio?", Actas del trigésimo octavo simposio anual ACM sobre teoría de la computación - STOC '06 , p. 373, doi : 10.1145 / 1132516.1132571 , ISBN 978-1595931344
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
2008
Jennifer Rexford (2008), "Rethinking Internet routing", Actas del cuadragésimo simposio anual de ACM sobre teoría de la computación - STOC 08 , págs. 55–56, doi : 10.1145 / 1374376.1374386 , ISBN 9781605580470
David Haussler (2008), "Computación cómo nos convertimos en humanos", Actas del cuadragésimo simposio anual de ACM sobre teoría de la computación - STOC 08 , págs. 639–640, doi : 10.1145 / 1374376.1374468 , ISBN 9781605580470
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
2009
Shafi Goldwasser (2009), "Athena lecture: Controlling Access to Programs?", Actas del 41º simposio anual de ACM sobre el 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 ACM Turing 2010)
Ravi Kannan (2011), "Algoritmos: aspectos destacados y desafíos recientes" (Conferencia del Premio Knuth 2011)
David A. Ferruci (2011), "IBM's Watson / DeepQA" (Charla plenaria de la FCRC)
Luiz Andre Barroso (2011), "Computación a escala de almacén: Entrar en 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), "Pruebas según Silvio" (Conferencia Premio Turing) video
2015
Michael Stonebraker (2015), Conferencia del Premio Turing video
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 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 TdC" (Charla principal)
Orna Kupferman (2017), "Examinar los problemas clásicos de la teoría de grafos desde el punto de vista de los métodos de verificación formal" (Keynote Talk)
Oded Goldreich (2017), Conferencia del Premio Knuth

Ver también

Notas

Referencias

enlaces externos