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

Премия Гёделя (англ. 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Андрей Булатов, Jin-Yi Cai, Xi Chen, Martin Dyer, David Richerbyfor their work on the classification of the counting complexity of constraint satisfaction problems

См. также

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

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.