Loading AI tools
Из Википедии, свободной энциклопедии
Премия Гёделя (англ. Gödel Prize) — премия в области теории вычислительных систем имени Курта Гёделя, вручаемая ежегодно организациями 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 | Жеро Сенизерг[англ.] | за доказательство разрешимости эквивалентности детерминированных автоматов с магазинной памятью[20][21]. |
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] |
2024 | Райан Уильямс | за его работы по нижним оценкам для схем и парадигму "нижние оценки из алгоритмов"[51] |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.