Из Википедии, бесплатной энциклопедии
  (Перенаправлено из STOC )
Перейти к навигации Перейти к поиску

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

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

Награды [ править ]

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

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

История [ править ]

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

Ранние основополагающие статьи в STOC включают Cook (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, doi : 10.1145 / 1007352.1007356 , ISBN 978-1581138528
Ави Вигдерсон (2004), «Глубина в ширину, или почему мы должны посещать переговоры в других областях?», Материалы тридцать шестого ежегодного симпозиума ACM по теории вычислений - STOC '04 , стр. 579, DOI : 10,1145 / 1007352,1007359 , ISBN 978-1581138528
2005 г.
Лэнс Фортноу (2005), «Помимо NP: работа и наследие Ларри Стокмейера», Труды тридцать седьмого ежегодного симпозиума ACM по теории вычислений - STOC '05 , стр. 120, DOI : 10.1145 / 1060590.1060609 , ISBN 978-1581139600
2006 г.
Прабхакар Рагхаван (2006), «Меняющийся облик веб-поиска: алгоритмы, аукционы и реклама», Труды тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 , стр. 129, DOI : 10,1145 / 1132516,1132535 , ISBN 978-1595931344
Рассел Импальяццо (2006), «Можно ли дерандомизировать каждый рандомизированный алгоритм?», Труды тридцать восьмого ежегодного симпозиума ACM по теории вычислений - STOC '06 , стр. 373, DOI : 10,1145 / 1132516,1132571 , ISBN 978-1595931344
2007 г.
Нэнси Линч (2007), "Теория распределенных вычислений: алгоритмы, результаты невозможности, модели и доказательства", Труды тридцать девятого ежегодного симпозиума ACM по теории вычислений - STOC '07 , стр. 247, DOI : 10,1145 / 1250790,1250826 , ISBN 9781595936318
2008 г.
Дженнифер Рексфорд (2008), «Переосмысление интернет-маршрутизации», Труды сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08 , стр. 55, DOI : 10,1145 / 1374376,1374386 , ISBN 9781605580470
Дэвид Хаусслер (2008), «Вычисление, как мы стали людьми», Труды сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08 , стр. 639, DOI : 10,1145 / 1374376,1374468 , ISBN 9781605580470
Райан О'Доннелл (2008), "Некоторые темы анализа булевых функций", Труды сорокового ежегодного симпозиума ACM по теории вычислений - STOC 08 , стр. 569, DOI : 10,1145 / 1374376,1374458 , ISBN 9781605580470
2009 г.
Гольдвассер (2009), «Афина Лекция: Управление доступом к программам?», Труды 41 - й ежегодный симпозиум по ACM симпозиум по теории вычислительных - STOC '09 , стр 167-168,. DOI : 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), «Исследование классических задач теории графов с точки зрения методов формальной проверки» (Keynote Talk)
Одед Гольдрайх (2017), лекция о премии Кнута

См. Также [ править ]

  • Конференции по теоретической информатике.
  • Список конференций по информатике содержит другие научные конференции по информатике.
  • Список наград в области информатики

Заметки [ править ]

  1. ^ "Труды 44-го симпозиума по теории вычислений" . 2012 . Проверено 17 сентября 2012 .
  2. ^ «Звания конференции» . Проверено 30 августа 2016 .
  3. ^ "Награды за лучшую работу конференции STOC" . Проверено 7 апреля 2012 .
  4. ^ "Премия Дэнни Левина за лучшую студенческую работу" . Архивировано из оригинала на 2008-06-20.
  5. Перейти ↑ Leighton, Tom (2002). «Замечания Тома Лейтона в ознаменование присвоения награды STOC за лучшую студенческую работу в честь покойного Дэниела Левина» .
  6. ^ Proc. STOC 1969. DOI : 10,1145 / 800169 .

Ссылки [ править ]

  • Кук, Стивен (1971), "Сложность процедур доказательства теорем", Proc. STOC 1971 (PDF) . С. 151-158, DOI : 10,1145 / 800157,805047.
  • Фич, Вера (1996), «Вопросы инфраструктуры, связанные с теорией компьютерных исследований», ACM Computing Surveys , 28 (4es): 217 – es, doi : 10.1145 / 242224.242502.
  • Джонсон, DS (1984), "Генеалогия теоретической информатики: предварительный отчет", ACM SIGACT News , 16 (2): 36-49, DOI : 10,1145 / 1008959,1008960.

Внешние ссылки [ править ]

  • Официальный веб-сайт
  • Информация о судебных разбирательствах по делу STOC в DBLP .
  • Материалы STOC в цифровой библиотеке ACM .
  • Статистика цитирования для FOCS / STOC / SODA , Петр Индик и Суреш Венкатасубраманян , июль 2007 г.