Симпозиум по теории вычислений
Конференция по теоретической информатике

Ежегодный симпозиум 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] для признания работ самого высокого качества на конференции. Кроме того, премия Danny Lewin Best Student Paper Award присуждается автору(ам) лучшей студенческой работы в 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, doi :10.1145/1007352.1007359, ISBN 978-1581138528, S2CID  27563516
2005
Лэнс Фортноу (2005), «За пределами NP: работа и наследие Ларри Стокмейера», Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '05 , стр. 120, doi :10.1145/1060590.1060609, ISBN 978-1581139600, S2CID  16558679
2006
Прабхакар Рагхаван (2006), «Изменение облика веб-поиска: алгоритмы, аукционы и реклама», Труды тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 , стр. 129, doi :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, doi :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), лекция на премию Кнута
Оливье Темам (2015), основная лекция FCRC
2016
Сантош Вемпала (2016), «Взаимодействие выборки и оптимизации в больших измерениях» (приглашенный доклад)
Тимоти Чан (2016), «Вычислительная геометрия от низких до высоких измерений» (приглашенный доклад)
2017
Ави Вигдерсон (2017), «О природе и будущем ToC» (основной доклад)
Орна Купферман (2017), «Исследование классических проблем теории графов с точки зрения методов формальной проверки» (основной доклад)
Одед Голдрайх (2017), лекция о премии Кнута

Смотрите также

Примечания

  1. ^ "Труды 44-го симпозиума по теории вычислений". 2012. Получено 17 сентября 2012 г.
  2. ^ "Ранги конференции" . Получено 2016-08-30 .
  3. ^ "Премии за лучшую работу конференции STOC" . Получено 07.04.2012 .
  4. ^ "Премия Дэнни Левина за лучшую студенческую работу". Архивировано из оригинала 2008-06-20.
  5. ^ Лейтон, Том (2002). «Замечания Тома Лейтона в ознаменование присвоения премии STOC за лучшую студенческую работу имени покойного Дэниела Левина».
  6. ^ Учеб. STOC 1969. doi : 10.1145/800169.

Ссылки

  • Кук, Стивен (1971), «Сложность процедур доказательства теорем» (PDF) , Proc. STOC 1971 , стр.  151–158 , doi : 10.1145/800157.805047 , S2CID  7573663.
  • Fich, Faith (1996), «Вопросы инфраструктуры, связанные с теорией исследований вычислений», ACM Computing Surveys , 28 (4es): 217–es, doi : 10.1145/242224.242502, S2CID  195706843.
  • Джонсон, Д.С. (1984), «Генеалогия теоретической информатики: предварительный отчет», ACM SIGACT News , 16 (2): 36–49 , doi :10.1145/1008959.1008960, S2CID  26789249.
Взято с "https://en.wikipedia.org/w/index.php?title=Симпозиум_по_теории_вычислительной_информатики&oldid=1245801400"