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