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
- Conferencias en informática teórica.
- La lista de conferencias de informática contiene otras conferencias académicas en informática.
- Lista de premios de informática
Notas
Referencias
- Cook, Stephen (1971), "La complejidad de los procedimientos de demostración de teoremas" (PDF) , Proc. STOC 1971 , págs. 151-158, doi : 10.1145 / 800157.805047.
- Fich, Faith (1996), "Problemas de infraestructura relacionados con la teoría de la investigación informática", Encuestas de computación de ACM , 28 (4es): 217 – es, doi : 10.1145 / 242224.242502.
- Johnson, DS (1984), "La genealogía de la informática teórica: un informe preliminar", ACM SIGACT News , 16 (2): 36–49, doi : 10.1145 / 1008959.1008960.