Премия Гёделя

Премия Гёделя (англ. 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	Ласло Бабаи, Шафи Гольдвассер, Сильвио Микали, Шломо Моран и Чарльз Ракофф	за разработку интерактивных систем доказательств.
1994	Йохан Хостад	за доказательство экспоненциальной нижней оценки на подсчёт чётности при помощи булевых схем константной глубины.
1995	Нил Иммерман, Роберт Шелепченьи	за теорему Иммермана — Шелепченьи (теория сложности вычислений).
1996	Марк Джеррам, Элистер Синклер	за исследования цепей Маркова и аппроксимацию перманента матриц.
1997	Джозеф Хэлперн, Йорам Мозес	за формальное определение понятия «знание» в распределённых средах.
1998	Сэйносукэ Тода	за теорему Тода, которая показала связь между классами сложности PP и PH.
1999	Питер Шор	за алгоритм Шора для факторизации чисел за полиномиальное количество времени на квантовом компьютере.
2000	Моше Варди, Пьер Вольпер	за исследование проверки моделей с помощью конечных автоматов.
2001	Санджив Арора, Уриэль Фейге, Шафи Гольдвассер, Карстен Лунд, Ласло Ловас, Раджив Мотвани, Шмуель Сафра, Мадху Судан, Марио Сегеди	за теорему PCP и её приложение.
2002	Жеро Сенизерг	за доказательство разрешимости эквивалентности детерминированных автоматов с магазинной памятью.
2003	Йоав Фройнд и Роберт Шапире	за алгоритм AdaBoost.
2004	Морис Херлихи, Майкл Сакс, Нир Шавит и Фотиос Захароглу	за приложение топологии в теории распределённых вычислений.
2005	Нога Алон, Йосси Матиас, Марио Сегеди	за основополагающие исследования в области потоковых алгоритмов.
2006	Маниндра Агравал, Нирадж Кайал, Нитин Саксена	за тест Агравала — Каяла — Саксены.
2007	Александр Разборов, Стивен Рудич	за «естественные доказательства».
2008	Тэн Шанхуа, Дэниэл Спилмен	за «сглаженный анализ» алгоритмов.
2009	Омер Рейнгольд, Салил Вадхан, Ави Вигдерсон	за зигзаг-произведение графов и нахождение логарифмического по памяти детерминированного алгоритма решения задачи неориентированной st-связности.
2010	Санджив Арора, Джозеф Митчелл	за открытие полиномиальной по времени приближённой схемы (PTAS) для евклидовой задачи коммивояжёра.
2011	Йохан Хостад	за доказательство неаппроксимируемости для различных комбинаторных задач.
2012	Элиас Куцупиас, Христос Пападимитриу, Тим Роухгарден, Эва Тардош, Ноам Нисан, Амир Ронен	за вклад в понимание того, как эгоистичное поведение пользователей и поставщиков услуг влияет на поведение Интернета и других сложных вычислительных систем.
2013	Антуан Жу, Дэн Боне, Мэтью К. Франклин	за работы по криптографии.
2014	Роналд Фэгин, Амнон Лотем, Мони Наор	за алгоритмы оптимальной агрегации для Middleware.
2015	Дэниэл Спилмен, Тэн Шанхуа	за серию работ о быстром решении систем линейных уравнений.
2016	Стивен Брукс, Питер О'Хёрн	за разработку параллельной логики разделения.
2017	Синтия Дворк, Фрэнк Макшерри, Коби Ниссим, Адам Д. Смит	Дифференциальная приватность.
2018	Одед Регев	Обучение с ошибками.
2019	Ирит Динур	за новое, более простое доказательство теоремы PCP методом усиления щелей.
2020	Робин Мозер и Габор Тардос	за алгоритмическую версию локальной леммы Ловаса
2021	Андрей Булатов, Jin-Yi Cai, Xi Chen, Martin Dyer, David Richerby	for their work on the classification of the counting complexity of constraint satisfaction problems

См. также

• Курт Гёдель
• Премия Кнута
• Список премий в информатике

Ссылки

• ACM SIGACT — Gödel Prize Архивная копия от 9 июля 2019 на Wayback Machine (англ.)
• Gödel Prize (together with ACM SIGACT) Архивная копия от 29 марта 2018 на Wayback Machine Премия Гёделя на сайте EATCS (англ.)