Премия Гёделя
Премия Гёделя (
ACM SIGACT, (Special Interest Group on Algorithms and Computation Theory) и EATCS, (European Association for Theoretical Computer Science) за выдающиеся труды по логике и теоретической информатике
.
Премия вручается с 1993 года и сопровождается денежным вознаграждением размером в 5000 долларов США[1]. Награждение проходит либо на американском симпозиуме STOC , (Symposium on Theory of Computing), либо на европейской конференции ICALP , (International Colloquium on Automata, Languages and Programming). Основным требованием к работе является дата первой публикации — к номинации допускаются лишь труды не старше 14 лет.
Лауреаты
Год | Имя | Примечания |
---|---|---|
1993 |
Ласло Бабаи, Шафи Гольдвассер, Сильвио Микали, Шломо Моран и Чарльз Ракофф | за разработку интерактивных систем доказательств[2][3]. |
1994 |
Йохан Хостад | за доказательство экспоненциальной нижней оценки на подсчёт чётности при помощи булевых схем константной глубины[4][5]. |
1995 |
Нил Иммерман , Роберт Шелепченьи | за теорему Иммермана — Шелепченьи (теория сложности вычислений)[6][7]. |
1996 |
Марк Джеррам , Элистер Синклер | за исследования цепей Маркова и аппроксимацию перманента матриц[8][9]. |
1997 |
Джозеф Хэлперн , Йорам Мозес | за формальное определение понятия «знание» в распределённых средах[10][11]. |
1998 |
Сэйносукэ Тода | за теорему Тода , которая показала связь между классами сложности PP и PH[12][13]. |
1999 |
Питер Шор | за алгоритм Шора для факторизации чисел за полиномиальное количество времени на квантовом компьютере[14][15]. |
2000 |
Моше Варди, Пьер Вольпер | за исследование проверки моделей с помощью конечных автоматов[16][17]. |
2001 |
Санджив Арора, Уриэль Фейге, Шафи Гольдвассер, Карстен Лунд , Ласло Ловас, Раджив Мотвани, Шмуель Сафра , Мадху Судан, Марио Сегеди | за теорему PCP и её приложение[18][19]. |
2002 |
Жеро Сенизерг | за доказательство . |
2003 |
Йоав Фройнд и Роберт Шапире | за алгоритм AdaBoost[22][23]. |
2004 |
Морис Херлихи, Майкл Сакс , Нир Шавит и Фотиос Захароглу | за приложение топологии в теории распределённых вычислений[24][25]. |
2005 |
Нога Алон, Йосси Матиас , Марио Сегеди | за основополагающие исследования в области потоковых алгоритмов[26][27]. |
2006 |
Маниндра Агравал , Нирадж Кайал , Нитин Саксена | за тест Агравала — Каяла — Саксены[28][29]. |
2007 |
Александр Разборов, Стивен Рудич | за «естественные доказательства»[30][31]. |
2008 |
Дэниэл Спилмен |
за «сглаженный анализ» алгоритмов[32]. |
2009 |
Ави Вигдерсон |
за логарифмического по памяти детерминированного алгоритма решения задачи неориентированной st-связности[33] .
|
2010 |
Санджив Арора, Джозеф Митчелл | за открытие полиномиальной по времени приближённой схемы (PTAS) для евклидовой задачи коммивояжёра[34]. |
2011 |
Йохан Хостад | за доказательство неаппроксимируемости для различных комбинаторных задач[35]. |
2012 |
Элиас Куцупиас , Христос Пападимитриу, Тим Роухгарден , Эва Тардош, Ноам Нисан , Амир Ронен | за вклад в понимание того, как эгоистичное поведение пользователей и поставщиков услуг влияет на поведение Интернета и других сложных вычислительных систем[36]. |
2013 |
Антуан Жу , Дэн Боне, Мэтью К. Франклин | за работы по криптографии[37][38]. |
2014 |
Роналд Фэгин , Амнон Лотем , Мони Наор | за алгоритмы оптимальной агрегации для Middleware[39]. |
2015 |
Дэниэл Спилмен, Тэн Шанхуа |
за серию работ о быстром решении систем линейных уравнений[40][41]. |
2016 |
Стивен Брукс , Питер О'Хёрн | за разработку параллельной логики разделения[42]. |
2017 |
Синтия Дворк, Фрэнк Макшерри , Коби Ниссим , Адам Д. Смит | Дифференциальная приватность[43]. |
2018 |
Одед Регев | Обучение с ошибками[44]. |
2019 |
Ирит Динур[45] | за новое, более простое доказательство теоремы PCP методом увеличения зазора[46]. |
2020 |
Робин Мозер и Габор Тардос | за алгоритмическую версию локальной леммы Ловаса[47] |
2021 |
Андрей Булатов, Джин-И Цай , Си Чэнь , Мартин Дайер и Дэвид Ричерби | за работу по классификации сложности вычислений в задачах по удовлетворению ограничений[48] |
2022 |
Цвика Бракерски , Крейг Джентри и Винод Вайкунтанатан | за новаторский вклад в криптографию при помощи создания схем полностью гомоморфного шифрования[49] |
2023 |
Самуэль Фиорини, Серж Массар и Себастьян Покутта, Ханс Радж Тивари, Рональд де Вольф и Томас Ротвосс | за показ того, что дополнение формулы решения проблемы коммивояжёра приводит к экспотенциальному росту многоугольника[50] |
См. также
Примечания
- ↑ 2017 Gödel Prize . European Association for Theoretical Computer Science. EATCS. Дата обращения: 29 марта 2017. Архивировано 16 апреля 2019 года.
- ↑ 1993 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 1 ноября 2021 года.
- ↑ Gödel Prize — 1993 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 1994 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ Gödel Prize — 1994 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 1995 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ Gödel Prize — 1995 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 1996 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ Gödel Prize — 1996 . Дата обращения: 11 июля 2019. Архивировано 22 июля 2019 года.
- ↑ 1997 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 1 ноября 2021 года.
- ↑ Gödel Prize — 1997 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 1998 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ Gödel Prize — 1998 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 1999 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 6 августа 2020 года.
- ↑ Gödel Prize — 1999 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 2000 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ Gödel Prize — 2000 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 2001 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 22 апреля 2021 года.
- ↑ Gödel Prize — 2001 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 2002 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 1 ноября 2021 года.
- ↑ Gödel Prize — 2002 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 2003 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 13 апреля 2021 года.
- ↑ Gödel Prize — 2003 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 2004 Gödel Prize . Дата обращения: 2 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ Gödel Prize — 2004 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 2005 Gödel Prize . Дата обращения: 2 июля 2019. Архивировано 1 ноября 2021 года.
- ↑ Gödel Prize — 2005 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 2006 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ Gödel Prize — 2006 . Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
- ↑ 2007 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ Gödel Prize — 2007 . Дата обращения: 12 апреля 2018. Архивировано 12 апреля 2018 года.
- ↑ 2008 Godel Prize . Дата обращения: 1 июля 2019. Архивировано 1 ноября 2021 года.
- ↑ 2009 Gödel Prize . Дата обращения: 11 июля 2019. Архивировано 7 января 2021 года.
- ↑ 2010 Godel Prize . Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ 2011 Godel Prize . Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
- ↑ "Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory". 2012-05-16. Архивировано из оригинала 18 июля 2013. Дата обращения: 16 мая 2012.
- ↑ Gödel Prize — 2013 . Дата обращения: 12 июля 2019. Архивировано 12 июля 2019 года.
- ↑ ACM Group Presents Gödel Prize for Advances in Cryptography — Association for Computing Machinery Архивировано 1 июня 2013 года.
- ↑ Gödel Prize 2014 . Дата обращения: 12 апреля 2018. Архивировано 13 апреля 2018 года.
- ↑ 2015 Gödel Prize . Дата обращения: 1 июля 2019. Архивировано 21 мая 2020 года.
- ↑ Gödel Prize 2015 . Дата обращения: 12 июля 2019. Архивировано 12 июля 2019 года.
- ↑ 2016 Gödel Prize . Дата обращения: 15 января 2017. Архивировано 6 февраля 2017 года.
- ↑ 2017 Gödel Prize . Дата обращения: 6 мая 2019. Архивировано 11 июля 2017 года.
- ↑ 2018 Gödel Prize . Дата обращения: 12 апреля 2018. Архивировано 5 октября 2018 года.
- ↑ Knuth and Gödel Prizes to be Awarded at 2019 ACM SIGACT Conference . Дата обращения: 22 июня 2019. Архивировано 22 июня 2019 года.
- ↑ 2019 Gödel Prize citation . Дата обращения: 6 мая 2019. Архивировано 28 июля 2020 года.
- ↑ 2020 Gödel Prize . Дата обращения: 13 мая 2020. Архивировано 16 июля 2020 года.
- ↑ 2021 Gödel Prize citation .
- ↑ 2022 Gödel Prize citation .
- ↑ 2023 Gödel Prize citation .
Ссылки
- ACM SIGACT — Gödel Prize Архивная копия от 9 июля 2019 на Wayback Machine (англ.)
- Gödel Prize (together with ACM SIGACT) Архивная копия от 29 марта 2018 на Wayback Machine Премия Гёделя на сайте EATCS (англ.)