Информационные списки

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

Перейти к навигацииПерейти к поиску

Курт Гёдель в 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". 2012-05-16. Архивировано из оригинала 18 июля 2013. Дата обращения: 16 мая 2012.
  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.

Ссылки