Симпозиум по теории вычислений - Symposium on Theory of Computing

В Ежегодный симпозиум ACM по теории вычислений (STOC) является научная конференция в области теоретическая информатика. STOC организуется ежегодно с 1969 года, обычно в мае или июне; конференцию спонсирует Ассоциация вычислительной техники группа особых интересов SIGACT. Уровень принятия STOC, в среднем с 1970 по 2012 год, составляет 31%, с темпом 29% в 2012 году.[1]

Так как Фич (1996) пишет, STOC и его ежегодный IEEE аналог FOCS ( Симпозиум по основам информатики ) считаются двумя ведущими конференциями в области теоретической информатики,[2] рассматриваются в широком смысле: они «являются форумами для некоторых из лучших работ по теории вычислений, которые способствуют расширению круга исследователей теории вычислений и помогают сплотить сообщество». Джонсон (1984) включает регулярное посещение STOC и FOCS как одну из нескольких определяющих характеристик ученых-теоретиков.

Награды

В Премия Гёделя для выдающихся работ по теоретической информатике представлен попеременно в STOC и на Международный коллоквиум по автоматам, языкам и программированию (ИКАЛП); то Приз Кнута за выдающийся вклад в основы информатики представлен попеременно на STOC и на FOCS.

С 2003 года STOC вручает одну или несколько наград Best Paper Awards.[3] отмечать на конференции доклады высочайшего качества. Кроме того, награда Дэнни Левина за лучшую студенческую работу присуждается авторам лучшей студенческой работы в STOC.[4] Премия названа в честь Дэниел М. Левин, американо-израильский математик и предприниматель, соучредитель интернет-компании Akamai Technologies, и был одной из первых жертв 11 сентября нападения.[5]

История

STOC был впервые организован 5–7 мая 1969 г. в г. Марина дель Рей, Калифорния, Соединенные Штаты. Председателем конференции был Патрик К. Фишер, а программный комитет состоял из Майкл А. Харрисон, Роберт В. Флойд, Юрис Хартманис, Ричард М. Карп, Альберт Р. Мейер, и Джеффри Д. Уллман.[6]

Ранние основополагающие статьи в STOC включают: Повар (1971), который ввел понятие NP-полнота (смотрите также Теорема Кука – Левина ).

Расположение

STOC был организован в Канада в 1992, 1994, 2002 и 2008 годах, а в Греция в 2001; все остальные собрания в 1969–2009 гг. проводились в Соединенные Штаты. STOC был частью Конференция по исследованиям федеративных вычислений (FCRC) в 1993, 1996, 1999, 2003, 2007 и 2011 годах.

Приглашенные спикеры

2004
Эва Тардос (2004), «Сетевые игры», Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04, стр. 341–342, Дои:10.1145/1007352.1007356, ISBN  978-1581138528
Ави Вигдерсон (2004), «Глубина в ширину, или зачем нам посещать переговоры в других областях?», Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04, п. 579, г. Дои:10.1145/1007352.1007359, ISBN  978-1581138528
2005
Лэнс Фортноу (2005), «За пределами NP: работа и наследие Ларри Стокмейера», Материалы тридцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '05, п. 120, Дои:10.1145/1060590.1060609, ISBN  978-1581139600
2006
Прабхакар Рагхаван (2006), «Меняющийся облик веб-поиска: алгоритмы, аукционы и реклама», Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06, п. 129, Дои:10.1145/1132516.1132535, ISBN  978-1595931344
Рассел Импальяццо (2006), «Можно ли дерандомизировать любой рандомизированный алгоритм?», Материалы тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06, п. 373, г. Дои:10.1145/1132516.1132571, ISBN  978-1595931344
2007
Нэнси Линч (2007), «Теория распределенных вычислений: алгоритмы, результаты невозможности, модели и доказательства», Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений - STOC '07, п. 247, Дои:10.1145/1250790.1250826, ISBN  9781595936318
2008
Дженнифер Рексфорд (2008), «Переосмысление интернет-маршрутизации», Материалы сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08, п. 55, Дои:10.1145/1374376.1374386, ISBN  9781605580470
Дэвид Хаусслер (2008), «Расчеты, как мы стали людьми», Материалы сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08, п. 639, г. Дои:10.1145/1374376.1374468, ISBN  9781605580470
Райан О'Доннелл (2008), «Некоторые вопросы анализа булевых функций», Материалы сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08, п. 569, г. Дои:10.1145/1374376.1374458, ISBN  9781605580470
2009
Шафи Гольдвассер (2009), «Лекция Афины: Контроль доступа к программам?», Материалы 41-го ежегодного симпозиума ACM по теории вычислений - STOC '09, стр. 167–168, Дои:10.1145/1536414.1536416, ISBN  9781605585062
2010
Дэвид С. Джонсон (2010), «Аппроксимационные алгоритмы в теории и практике» (лекция по премии Кнута)
2011
Лесли Г. Валиант (2011), «Степень и ограничения механистических объяснений природы» (лекция 2010 ACM Turing Award)
Рави Каннан (2011), «Алгоритмы: последние моменты и вызовы» (лекция премии Кнута 2011 г.)
Дэвид А. Ферручи (2011), "IBM's 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. Получено 2012-09-17.
  2. ^ «Рейтинги конференции». Получено 2016-08-30.
  3. ^ "Награда за лучшую бумагу конференции STOC". Получено 2012-04-07.
  4. ^ «Премия Дэнни Левина за лучшую студенческую работу». Архивировано из оригинал на 20.06.2008.
  5. ^ Лейтон, Том (2002). «Замечания Тома Лейтона в ознаменование присвоения награды STOC за лучшую студенческую работу в честь покойного Дэниела Левина».
  6. ^ Proc. STOC 1969.

использованная литература

внешние ссылки