Jump to content

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

Ежегодный симпозиум 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), лекция на премию Кнута

См. также

[ редактировать ]

Примечания

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: d552968f0dad5928d6283e51de34e311__1702483020
URL1:https://arc.ask3.ru/arc/aa/d5/11/d552968f0dad5928d6283e51de34e311.html
Заголовок, (Title) документа по адресу, URL1:
Symposium on Theory of Computing - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)