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

Курт Гёдель в 1925 году

Премия Гёделя (англ. 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]

См. также

Примечания

  1. ↑ 2017 Gödel Prize. European Association for Theoretical Computer Science. EATCS. Дата обращения: 29 марта 2017. Архивировано 16 апреля 2019 года.
  2. ↑ 1993 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 1 ноября 2021 года.
  3. ↑ Gödel Prize — 1993. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  4. ↑ 1994 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
  5. ↑ Gödel Prize — 1994. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  6. ↑ 1995 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
  7. ↑ Gödel Prize — 1995. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  8. ↑ 1996 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
  9. ↑ Gödel Prize — 1996. Дата обращения: 11 июля 2019. Архивировано 22 июля 2019 года.
  10. ↑ 1997 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 1 ноября 2021 года.
  11. ↑ Gödel Prize — 1997. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  12. ↑ 1998 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
  13. ↑ Gödel Prize — 1998. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  14. ↑ 1999 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 6 августа 2020 года.
  15. ↑ Gödel Prize — 1999. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  16. ↑ 2000 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
  17. ↑ Gödel Prize — 2000. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  18. ↑ 2001 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 22 апреля 2021 года.
  19. ↑ Gödel Prize — 2001. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  20. ↑ 2002 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 1 ноября 2021 года.
  21. ↑ Gödel Prize — 2002. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  22. ↑ 2003 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 13 апреля 2021 года.
  23. ↑ Gödel Prize — 2003. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  24. ↑ 2004 Gödel Prize. Дата обращения: 2 июля 2019. Архивировано 4 ноября 2021 года.
  25. ↑ Gödel Prize — 2004. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  26. ↑ 2005 Gödel Prize. Дата обращения: 2 июля 2019. Архивировано 1 ноября 2021 года.
  27. ↑ Gödel Prize — 2005. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  28. ↑ 2006 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
  29. ↑ Gödel Prize — 2006. Дата обращения: 11 июля 2019. Архивировано 12 октября 2019 года.
  30. ↑ 2007 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
  31. ↑ Gödel Prize — 2007. Дата обращения: 12 апреля 2018. Архивировано 12 апреля 2018 года.
  32. ↑ 2008 Godel Prize. Дата обращения: 1 июля 2019. Архивировано 1 ноября 2021 года.
  33. ↑ 2009 Gödel Prize. Дата обращения: 11 июля 2019. Архивировано 7 января 2021 года.
  34. ↑ 2010 Godel Prize. Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
  35. ↑ 2011 Godel Prize. Дата обращения: 11 июля 2019. Архивировано 4 ноября 2021 года.
  36. ↑ "Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory". 16 мая 2012. Архивировано из оригинала 18 июля 2013. Дата обращения: 16 мая 2012. {cite news}: |archive-date= / |archive-url= несоответствие временной метки; предлагается 18 июля 2013 (справка)
  37. ↑ Gödel Prize — 2013. Дата обращения: 12 июля 2019. Архивировано 12 июля 2019 года.
  38. ↑ ACM Group Presents Gödel Prize for Advances in Cryptography — Association for Computing Machinery Архивировано 1 июня 2013 года.
  39. ↑ Gödel Prize 2014. Дата обращения: 12 апреля 2018. Архивировано 13 апреля 2018 года.
  40. ↑ 2015 Gödel Prize. Дата обращения: 1 июля 2019. Архивировано 21 мая 2020 года.
  41. ↑ Gödel Prize 2015. Дата обращения: 12 июля 2019. Архивировано 12 июля 2019 года.
  42. ↑ 2016 Gödel Prize. Дата обращения: 15 января 2017. Архивировано 6 февраля 2017 года.
  43. ↑ 2017 Gödel Prize. Дата обращения: 6 мая 2019. Архивировано 11 июля 2017 года.
  44. ↑ 2018 Gödel Prize. Дата обращения: 12 апреля 2018. Архивировано 5 октября 2018 года.
  45. ↑ Knuth and Gödel Prizes to be Awarded at 2019 ACM SIGACT Conference. Дата обращения: 22 июня 2019. Архивировано 22 июня 2019 года.
  46. ↑ 2019 Gödel Prize citation. Дата обращения: 6 мая 2019. Архивировано 28 июля 2020 года.
  47. ↑ 2020 Gödel Prize. Дата обращения: 13 мая 2020. Архивировано 16 июля 2020 года.
  48. ↑ 2021 Gödel Prize citation. Дата обращения: 27 марта 2024. Архивировано 4 июня 2022 года.
  49. ↑ 2022 Gödel Prize citation. Дата обращения: 27 марта 2024. Архивировано 31 октября 2022 года.
  50. ↑ 2023 Gödel Prize citation. Дата обращения: 27 марта 2024. Архивировано 22 июня 2023 года.
  51. ↑ 2024 Gödel Prize citation.

Ссылки