Симпозиум по теории вычислений

Симпозиум по теории вычислений (англ. Symposium on Theory of Computing, STOC) — ежегодная международная научная конференция, посвящённая фундаментальным вопросам теории вычислений. Проводится под эгидой Специальной группы по алгоритмам и теории вычислений (SIGACT) Ассоциации вычислительной техники (ACM). Является одним из двух наиболее престижных форумов в данной области наряду с Симпозиумом по основам информатики (FOCS).

История

Первый симпозиум состоялся в 1969 году в Марина-дель-Рей, Калифорния. Изначально он задумывался как площадка для обсуждения новых результатов в области автоматов, формальных языков и вычислимости. Организаторами выступили ведущие учёные того времени, включая Майкла Рабина и Дана Скотта.

К середине 1970-х годов тематика конференции расширилась, включив анализ алгоритмов, сложность вычислений и криптографию. В 1980-е годы, с развитием параллельных вычислений и теории приближённых алгоритмов, STOC стал ключевым местом для презентации работ по рандомизированным алгоритмам и интерактивным доказательствам.

С 1990-х годов конференция регулярно публикует труды (proceedings) в виде сборников, доступных в цифровой библиотеке ACM. В XXI веке STOC сохраняет статус главного события года для теоретиков информатики, собирая от 300 до 500 участников ежегодно.

Тематика и разделы

Программа симпозиума охватывает широкий спектр направлений теоретической информатики. Основные разделы включают:

• Алгоритмы и структуры данных: разработка и анализ эффективных алгоритмов для графов, строк, потоков данных и задач оптимизации.
• Теория сложности вычислений: классификация задач по классам сложности (P, NP, PSPACE, BPP и др.), изучение границ вычислимости.
• Криптография и безопасность: построение криптографических протоколов, доказательства безопасности, теория псевдослучайности.
• Квантовые вычисления: алгоритмы для квантовых компьютеров, квантовая сложность, квантовая коррекция ошибок.
• Теория обучения и искусственный интеллект: математические основы машинного обучения, PAC-обучение, теория игр и механизмов.
• Вычислительная биология и теория кодирования: алгоритмы для геномики, теория кодов, исправляющих ошибки.
• Распределённые вычисления и сети: алгоритмы для децентрализованных систем, консенсус, блокчейн.

Процедура рецензирования

STOC применяет двухэтапную систему рецензирования. На первом этапе авторы подают развёрнутые тезисы (extended abstracts) объёмом до 10 страниц. Программный комитет, состоящий из 30–40 ведущих специалистов, проводит анонимное рецензирование (double-blind). На втором этапе лучшие работы отбираются для устных или постерных презентаций.

Процент принятых статей традиционно низок — около 25–30%. Отбор основывается на новизне, строгости доказательств и потенциальном влиянии на область. После конференции авторы могут представить полные версии статей для публикации в рецензируемых журналах, таких как Journal of the ACM или SIAM Journal on Computing.

Награды

На симпозиуме ежегодно вручаются несколько престижных наград:

• Премия Гёделя (совместно с FOCS) — за выдающиеся работы по теоретической информатике. Вручается с 1993 года, лауреатами становились, например, Шафи Гольдвассер, Сильвио Микали, Ави Вигдерсон.
• Премия ACM SIGACT за выдающиеся заслуги — за вклад в развитие сообщества теоретиков.
• Премия за лучшую студенческую работу (Best Student Paper Award) — поощряет молодых исследователей.

Значение и влияние

STOC играет ключевую роль в формировании исследовательской повестки в теории вычислений. Многие фундаментальные результаты впервые были представлены именно на этой конференции:

• В 1971 году Стивен Кук представил свою работу «Сложность процедур доказательства теорем», заложившую основы теории NP-полноты.
• В 1985 году Ласло Бабаи представил протоколы интерактивных доказательств.
• В 1994 году Питер Шор анонсировал квантовый алгоритм факторизации, что стимулировало развитие квантовых вычислений.
• В 2002 году Суреш Венкатасубраманиан и его соавторы представили алгоритмы для приближённого решения задачи о клике.

Труды STOC цитируются в тысячах научных работ ежегодно. Конференция также служит площадкой для установления научных связей между университетами и исследовательскими центрами США, Европы, Израиля, Японии и Китая.

Критика

Некоторые исследователи отмечают, что высокий порог отбора на STOC может приводить к консерватизму в тематике и предпочтению «модных» направлений. Кроме того, географическое доминирование американских и европейских институтов иногда вызывает критику за недостаточную представленность учёных из развивающихся стран. В ответ на это организаторы в последние годы внедряют программы финансовой поддержки для участников из регионов с ограниченными ресурсами.

См. также

• Симпозиум по основам информатики (FOCS)
• Международный коллоквиум по автоматам, языкам и программированию (ICALP)
• Конференция по инновациям в теоретической информатике (ITCS)

Источники

• ACM SIGACT. STOC Conference History. Официальный сайт SIGACT.
• Cook, S. A. (1971). «The complexity of theorem-proving procedures». Proceedings of the third annual ACM symposium on Theory of computing.
• Goldwasser, S., Micali, S., Rackoff, C. (1985). «The knowledge complexity of interactive proof systems». Proceedings of the seventeenth annual ACM symposium on Theory of computing.
• Shor, P. W. (1994). «Algorithms for quantum computation: discrete logarithms and factoring». Proceedings 35th Annual Symposium on Foundations of Computer Science.
• Feige, U., et al. (2002). «Approximating the clique number». Proceedings of the thirty-fourth annual ACM symposium on Theory of computing.
• ACM Digital Library. Proceedings of the Annual ACM Symposium on Theory of Computing (1969–2024).