Jornada en informática teórica.
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 homólogo anual del IEEE, FOCS ( Simposio sobre fundamentos de la informática ), se consideran las dos principales conferencias en informática teórica, [2] consideradas en términos generales: "son foros para algunos de los mejores trabajos". en toda la teoría de la informática que promueven la amplitud entre los investigadores de la teoría de la informática 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 informática - 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 computación - 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), "IBM's Watson/DeepQA" (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
- ^ "Actas del 44º simposio sobre Teoría de la Computación". 2012 . Consultado el 17 de septiembre de 2012 .
- ^ "Rangos de conferencias" . Consultado el 30 de agosto de 2016 .
- ^ "Premios al mejor artículo de la conferencia STOC" . Consultado el 7 de abril de 2012 .
- ^ "Premio Danny Lewin al mejor artículo estudiantil". Archivado desde el original el 20 de junio de 2008.
- ^ 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".
- ^ Procedimiento. STOC 1969. doi : 10.1145/800169.
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 , S2CID 7573663.
- Fich, Faith (1996), "Problemas de infraestructura relacionados con la teoría de la investigación en informática", ACM Computing Surveys , 28 (4es): 217–es, doi :10.1145/242224.242502, S2CID 195706843.
- 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, S2CID 26789249.
Enlaces externos