Премия Гёделя () — премия в области теории вычислительных систем имени Курта Гёделя, вручаемая ежегодно организациями ACM SIGACT, (Special Interest Group on Algorithms and Computation Theory) и EATCS, (European Association for Theoretical Computer Science) за выдающиеся труды по логике и теоретической информатике.
Премия вручается с 1993 года и сопровождается денежным вознаграждением размером в 5000 долларов США. Награждение проходит либо на американском симпозиуме , (Symposium on Theory of Computing), либо на европейской конференции , (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 , , Ави Вигдерсон за зигзаг-произведение графов и нахождение логарифмического по памяти детерминированного алгоритма решения задачи . 2010 Санджив Арора, за открытие полиномиальной по времени приближённой схемы (PTAS) для евклидовой задачи коммивояжёра. 2011 за доказательство неаппроксимируемости для различных комбинаторных задач. 2012 , Христос Пападимитриу, , Эва Тардош, , за вклад в понимание того, как эгоистичное поведение пользователей и поставщиков услуг влияет на поведение Интернета и других сложных вычислительных систем. 2013 , Дэн Боне, за работы по криптографииACM Group Presents Gödel Prize for Advances in Cryptography — Association for Computing Machinery . 2014 , , за алгоритмы оптимальной агрегации для Middleware. 2015 Дэниэл Спилмен, Тэн Шанхуа за серию работ о быстром решении систем линейных уравнений. 2016 , за разработку параллельной логики разделения. 2017 Синтия Дворк, , , Дифференциальная приватность. 2018 Одед Регев Обучение с ошибками. 2019 Ирит Динур за новое, более простое доказательство теоремы PCP методом увеличения зазора. 2020 и за алгоритмическую версию локальной леммы Ловаса 2021 Андрей Булатов, , , и Дэвид Ричерби за работу по классификации сложности вычислений в задачах по удовлетворению ограничений 2022 , и за новаторский вклад в криптографию при помощи создания схем полностью гомоморфного шифрования 2023 Самуэль Фиорини, и Себастьян Покутта, Ханс Радж Тивари, Рональд де Вольф и Томас Ротвосс за доказательство того, что любая расширенная формулировка политопа для задачи коммивояжёра имеет экспоненциальный размер 2024 Райан Уильямс за его работы по нижним оценкам для схем и парадигму «нижние оценки из алгоритмов»
См. также Курт Гёдель Премия Кнута Список премий в информатике
Примечания
Ссылки
ACM SIGACT — Gödel Prize Gödel Prize (together with ACM SIGACT) Премия Гёделя на сайте EATCS
Гёдель Категория:Списки лауреатов премий Категория:Награды, появившиеся в 1993 году Категория:Награды по алфавиту Категория:Награды Ассоциации вычислительной техники