Ежегодный симпозиум ACM по теории вычислений ( STOC ) представляет собой научную конференцию в области теоретической информатики . STOC проводится ежегодно с 1969 года, обычно в мае или июне; Конференция спонсируется специальной группой Ассоциации вычислительной техники SIGACT . Уровень принятия STOC, в среднем с 1970 по 2012 год, составляет 31%, а в 2012 году - 29%. [1]
Как пишет Фич (1996) , STOC и его ежегодный аналог IEEE FOCS ( Симпозиум по основам компьютерных наук ) считаются двумя ведущими конференциями в теоретической информатике [2] в широком смысле: они «являются форумами для некоторых из лучших работ». всей теории вычислений, которые способствуют расширению круга исследователей теории вычислений и помогают сплотить сообщество». Джонсон (1984) включает регулярное посещение STOC и FOCS как одну из нескольких определяющих характеристик ученых-теоретиков в области информатики.
Премия Гёделя за выдающиеся работы в области теоретической информатики вручается поочередно на STOC и на Международном коллоквиуме по автоматам, языкам и программированию (ICALP); Премия Кнута за выдающийся вклад в основы информатики вручается поочередно в STOC и FOCS .
С 2003 года STOC вручает одну или несколько наград Best Paper Awards [3] для признания работ самого высокого качества на конференции. Кроме того, премия Дэнни Левина за лучшую студенческую работу присуждается автору (авторам) лучшей студенческой статьи в STOC. [4] Премия названа в честь Дэниела М. Левина , американо-израильского математика и предпринимателя, который стал соучредителем интернет-компании Akamai Technologies и стал одной из первых жертв терактов 11 сентября . [5]
Впервые STOC был организован 5–7 мая 1969 года в Марина-дель-Рей , Калифорния , США . Председателем конференции был Патрик С. Фишер , а в программный комитет входили Майкл А. Харрисон , Роберт У. Флойд , Юрис Хартманис , Ричард М. Карп , Альберт Р. Мейер и Джеффри Д. Ульман . [6]
Ранние основополагающие статьи в STOC включают Cook (1971) , который ввел понятие NP-полноты (см. также теорему Кука-Левина ).