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

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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Премия Гёделя (англ. Gödel Prize) — премия в области теории вычислительных систем имени Курта Гёделя, вручаемая ежегодно организациями ACM SIGACT, (Special Interest Group on Algorithms and Computation Theory) и EATCS, (European Association for Theoretical Computer Science) за выдающиеся труды по логике и теоретической информатике.

Премия вручается с 1993 года и сопровождается денежным вознаграждением размером в 5000 долларов США[1]. Награждение проходит либо на американском симпозиуме STOC[en], Symposium on Theory of Computing), либо на европейской конференции ICALP[en], International Colloquium on Automata, Languages and Programming). Основным требованием к работе является дата первой публикации — к номинации допускаются лишь труды не старше 14 лет.

Лауреаты[править | править код]

Год Имя Примечания
1993 Ласло Бабаи, Шафи Гольдвассер, Сильвио Микали, Шломо Моран и Чарльз Ракофф[en] за разработку интерактивных систем доказательств[en][2][3].
1994 Йохан Хостад[en] за доказательство экспоненциальной нижней оценки на подсчёт чётности при помощи булевых схем константной глубины[4][5].
1995 Нил Иммерман[en], Роберт Шелепченьи[en] за теорему Иммермана — Шелепченьи (теория сложности вычислений)[6][7].
1996 Марк Джеррам[en], Элистер Синклер[en] за исследования цепей Маркова и аппроксимацию перманента матриц[8][9].
1997 Джозеф Хэлперн[en], Йорам Мозес за формальное определение понятия «знание» в распределённых средах[10][11].
1998 Сэйносукэ Тода[en] за теорему Тода, которая показала связь между классами сложности PP и PH[12][13].
1999 Питер Шор за алгоритм Шора для факторизации чисел за полиномиальное количество времени на квантовом компьютере[14][15].
2000 Моше Варди, Пьер Вольпер[en] за исследование проверки моделей с помощью конечных автоматов[16][17].
2001 Санджив Арора, Уриэль Фейге, Шафи Гольдвассер, Карстен Лунд[en], Ласло Ловас, Раджив Мотвани, Шмуель Сафра[en], Мадху Судан, Марио Сегеди[en] за теорему PCP и её приложение[18][19].
2002 Жеро Сенизерг[en] за доказательство разрешимости эквивалентности детерминированных автоматов с магазинной памятью[20][21].
2003 Йоав Фройнд[en] и Роберт Шапире[en] за алгоритм AdaBoost[22][23].
2004 Морис Херлихи, Майкл Сакс[en], Нир Шавит и Фотиос Захароглу за приложение топологии в теории распределённых вычислений[24][25].
2005 Нога Алон, Йосси Матиас[en], Марио Сегеди[en] за основополагающие исследования в области потоковых алгоритмов[26][27].
2006 Маниндра Агравал[en], Нирадж Кайал[en], Нитин Саксена[en] за тест Агравала — Каяла — Саксены[28][29].
2007 Александр Разборов, Стивен Рудич[en] за «естественные доказательства»[30][31].
2008 Тэн Шанхуа, Дэниэл Спилмен за «сглаженный анализ» алгоритмов[32].
2009 Омер Рейнгольд[en], Салил Вадхан[en], Ави Вигдерсон за зигзаг-произведение графов и нахождение логарифмического по памяти детерминированного алгоритма решения задачи неориентированной st-связности (англ.)[33].
2010 Санджив Арора, Джозеф Митчелл[en] за открытие полиномиальной по времени приближённой схемы (PTAS) для евклидовой задачи коммивояжёра[34].
2011 Йохан Хостад[en] за доказательство неаппроксимируемости для различных комбинаторных задач[35].
2012 Элиас Куцупиас[fr], Христос Пападимитриу, Тим Роухгарден[en], Эва Тардош, Ноам Нисан[en], Амир Ронен[fr] за вклад в понимание того, как эгоистичное поведение пользователей и поставщиков услуг влияет на поведение Интернета и других сложных вычислительных систем[36].
2013 Антуан Жу[en], Дэн Бонех, Мэтью К. Франклин[en] за работы по криптографии[37][38].
2014 Роналд Фэгин[en], Амнон Лотем[fr], Мони Наор[en] за алгоритмы оптимальной агрегации для Middleware[39].
2015 Дэниэл Спилмен, Тэн Шанхуа за серию работ о быстром решении систем линейных уравнений[40][41].
2016 Стивен Брукс[fr], Питер О'Хёрн[en] за разработку многопоточной сепарационной логики[42].
2017 Синтия Дворк, Фрэнк Макшерри[fr], Коби Ниссим[fr], Адам Д. Смит[fr] Дифференциальная приватность[43].
2018 Одед Регев[fr] Обучение с ошибками[44].
2019 Ирит Динур[en][45] англ. for her new proof of the PCP Theorem by gap amplification[46].

См. также[править | править код]

Примечания[править | править код]

  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 May 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.

Ссылки[править | править код]