Симпозиум по теории вычислений
Ежегодный симпозиум 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 вручает одну или несколько наград за лучшую бумагу. [3] признавать доклады высочайшего качества на конференции. Кроме того, награда Дэнни Левина за лучшую студенческую работу присуждается автору(ам) лучшей студенческой статьи в STOC. [4] Премия названа в честь Дэниела М. Левина , американо-израильского математика и предпринимателя, который стал соучредителем интернет-компании Akamai Technologies и стал одной из первых жертв терактов 11 сентября . [5]
История
[ редактировать ]STOC был впервые организован 5–7 мая 1969 года в Марина-дель-Рей , Калифорния , США . Председателем конференции был Патрик К. Фишер , а в программный комитет входили Майкл А. Харрисон , Роберт В. Флойд , Юрис Хартманис , Ричард М. Карп , Альберт Р. Мейер и Джеффри Д. Ульман . [6]
Ранние плодотворные статьи в STOC включают Кука (1971) , который ввел концепцию NP-полноты (см. также теорему Кука – Левина ).
Расположение
[ редактировать ]STOC был организован в Канаде в 1992, 1994, 2002, 2008 и 2017 годах, в Греции в 2001 году как виртуальная/онлайн-конференция в 2020 и 2021 годах и в Италии в 2022 году; все остальные встречи в 1969–2023 гг. прошли в США . STOC был участником Федеративной конференции по компьютерным исследованиям (FCRC) в 1993, 1996, 1999, 2003, 2007, 2011, 2015, 2019 и 2023 годах.
Приглашенные спикеры
[ редактировать ]- 2004
- Ева Тардос (2004), «Сетевые игры», Труды тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04 , стр. 341–342, doi : 10.1145/1007352.1007356 , ISBN 978-1581138528 , S2CID 18249534
- Ави Вигдерсон (2004), «В глубину, или почему нам следует посещать переговоры в других областях?», Труды тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04 , стр. 579, номер домена : 10.1145/1007352.1007359 , ISBN 978-1581138528 , S2CID 27563516
- 2005
- Лэнс Фортноу (2005), «За пределами NP: работа и наследие Ларри Стокмейера», Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '05 , стр. 120, номер домена : 10.1145/1060590.1060609 , ISBN 978-1581139600 , S2CID 16558679
- 2006
- Прабхакар Рагхаван (2006), «Изменяющееся лицо веб-поиска: алгоритмы, аукционы и реклама», Труды тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 , стр. 129, номер домена : 10.1145/1132516.1132535 , ISBN 978-1595931344 , S2CID 19222958
- Рассел Импальяццо (2006), «Может ли каждый рандомизированный алгоритм быть дерандомизирован?», Труды тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 , стр. 373–374, doi : 10.1145/1132516.1132571 , ISBN 978-1595931344 , S2CID 22433370
- 2007
- Нэнси Линч (2007), «Теория распределенных вычислений: алгоритмы, результаты невозможности, модели и доказательства», Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений - STOC '07 , стр. 247, номер домена : 10.1145/1250790.1250826 , ISBN 9781595936318 , S2CID 22140755
- 2008
- Дженнифер Рексфорд (2008), «Переосмысление интернет-маршрутизации», Труды сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08 , стр. 55–56, doi : 10.1145/1374376.1374386 , ISBN 9781605580470 , S2CID 10958242
- Дэвид Хаусслер (2008), «Вычисления, как мы стали людьми», Труды сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08 , стр. 639–640, doi : 10.1145/1374376.1374468 , ISBN 9781605580470 , S2CID 30452365
- Райан О'Доннелл (2008), «Некоторые темы анализа логических функций», Труды сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08 , стр. 569–578, doi : 10.1145/1374376.1374458 , ISBN 9781605580470 , S2CID 1241681
- 2009
- Шафи Голдвассер (2009), «Лекция Афины: контроль доступа к программам?», Труды 41-го ежегодного симпозиума ACM по теории вычислений - STOC '09 , стр. 167–168, doi : 10.1145/1536414.1536416 , ISBN 9781605585062
- 2010
- Дэвид С. Джонсон (2010), «Алгоритмы аппроксимации в теории и практике» (лекция на премию Кнута)
- 2011
- Лесли Г. Валиант (2011), «Масштаб и ограничения механистических объяснений природы» (лекция на премию ACM Тьюринга 2010 г.)
- Рави Каннан (2011 г.), «Алгоритмы: последние достижения и проблемы» (лекция на премию Кнута 2011 г.)
- Дэвид А. Ферручи (2011), «IBM Watson/DeepQA» (пленарное выступление FCRC)
- Луис Андре Баррозу (2011), «Вычисления складского масштаба: вступление в подростковое десятилетие» (пленарный доклад FCRC)
- 2013
- Гэри Миллер (2013), лекция на премию Кнута
- Прабхакар Рагхаван (2013), пленарный доклад
- 2014
- Томас Ротвосс (2014), «Соответствующий многогранник имеет экспоненциальную сложность расширения»
- Шафи Гольдвассер (2014), «Криптографическая линза» (лекция на премию Тьюринга) видео
- Сильвио Микали (2014), «Доказательства по Сильвио» (лекция на премию Тьюринга) видео
- 2015
- Майкл Стоунбрейкер (2015), лекции на премию Тьюринга видео
- Эндрю Яо (2015), основная лекция FCRC
- Ласло Бабай (2015), лекция на премию Кнута
- Olivier Temam (2015), FCRC Keynote Lecture
- 2016
- Сантош Вемпала (2016), «Взаимодействие выборки и оптимизации в больших измерениях» (приглашенный доклад)
- Тимоти Чан (2016), «Вычислительная геометрия, от низкой к высокой размерности» (приглашенный доклад)
- 2017
- Ави Вигдерсон (2017), «О природе и будущем ToC» (основной доклад)
- Орна Купферман (2017), «Исследование классических задач теории графов с точки зрения методов формальной проверки» (основной доклад)
- Одед Гольдрейх (2017), лекция на премию Кнута
См. также
[ редактировать ]- Конференции по теоретической информатике.
- Список конференций по информатике содержит другие научные конференции по информатике.
- Список наград в области информатики
Примечания
[ редактировать ]- ^ «Материалы 44-го симпозиума по теории вычислений» . 2012 . Проверено 17 сентября 2012 г.
- ^ «Конференция рангов» . Проверено 30 августа 2016 г.
- ^ «Награда за лучшую работу конференции STOC» . Проверено 7 апреля 2012 г.
- ^ Премия Дэнни Левина за лучшую студенческую работу . Архивировано из оригинала 20 июня 2008 г.
- ^ Лейтон, Том (2002). «Замечания Тома Лейтона в честь присвоения премии STOC за лучшую студенческую работу в честь покойного Дэниела Левина» .
- ^ Учеб. СТОК 1969 года. дои : 10.1145/800169 .
Ссылки
[ редактировать ]- Кук, Стивен (1971), «Сложность процедур доказательства теорем» (PDF) , Proc. STOC 1971 , стр. 151–158, doi : 10.1145/800157.805047 , S2CID 7573663 .
- Фич, Фейт (1996), «Проблемы инфраструктуры, связанные с теорией компьютерных исследований», ACM Computing Surveys , 28 (4es): 217–es, doi : 10.1145/242224.242502 , S2CID 195706843 .
- Джонсон, DS (1984), «Генеалогия теоретической информатики: предварительный отчет», ACM SIGACT News , 16 (2): 36–49, doi : 10.1145/1008959.1008960 , S2CID 26789249 .
