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 entre 1970 y 2012, es del 31%, con una tasa del 29% en 2012. [1]
Como escribe Fich (1996) , STOC y su contraparte anual de IEEE FOCS (el Simposio sobre los fundamentos de la informática ) se consideran las dos principales conferencias en informática teórica, [2] consideradas ampliamente: “son foros para algunos de los mejores trabajos a través de 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 definitorias de los científicos informáticos teóricos.
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 [3] 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. [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]
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 . [6]
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 ).