Премия Гёделя
Премия в области компьютерных наук
Курт Гёдель
Курт Гёдель

Премия Гёделя — ежегодная премия за выдающиеся работы в области теоретической информатики , присуждаемая совместно Европейской ассоциацией теоретической информатики (EATCS) и Специальной группой по алгоритмам и теории вычислений Ассоциации вычислительной техники ( ACM SIGACT ). Премия названа в честь Курта Гёделя . Связь Гёделя с теоретической информатикой заключается в том, что он первым упомянул вопрос « P против NP » в письме 1956 года Джону фон Нейману , в котором Гёдель спрашивал, можно ли решить определенную NP-полную задачу за квадратичное или линейное время . [1]

Премия Гёделя вручается с 1993 года. Премия вручается поочередно на ICALP (четные годы) и STOC (нечетные годы). STOC — это ACM Symposium on Theory of Computing , одна из главных североамериканских конференций по теоретической информатике, тогда как ICALP — это International Colloquium on Automata, Languages ​​and Programming , одна из главных европейских конференций в этой области. Чтобы иметь право на премию, статья должна быть опубликована в рецензируемом журнале в течение последних 14 (ранее 7) лет. Премия включает вознаграждение в размере 5000 долларов США. [2]

Победитель премии выбирается комитетом из шести членов. Президент EATCS и председатель SIGACT назначают по три члена в комитет, которые будут работать поочередно в течение трех лет. Комитет возглавляют поочередно представители EATCS и SIGACT.

В отличие от премии Гёделя, которая присуждается за выдающиеся работы, премия Кнута присуждается отдельным лицам за их общий вклад в данную область.

Получатели

ГодИмя(я)ПримечанияГод публикации
1993Ласло Бабай , Шафи Гольдвассер , Сильвио Микали , Шломо Моран и Чарльз Ракоффдля разработки интерактивных систем доказательств1988, [статья 1] 1989 [статья 2]
1994Йохан Хостаддля экспоненциальной нижней границы размера булевых схем постоянной глубины (для функции четности ).1989 [статья 3]
1995Нил Иммерман и Роберт Селепшеньидля теоремы Иммермана–Селепченьи относительно недетерминированной пространственной сложности1988, [статья 4] 1988 [статья 5]
1996Марк Джеррум и Алистер Синклерза работу по цепям Маркова и приближению перманента матрицы1989, [статья 6] 1989 [статья 7]
1997Джозеф Халперн и Йорам Мозесдля определения формального понятия «знания» в распределенных средах1990 [статья 8]
1998Сейносукэ Тодадля теоремы Тоды , которая показала связь между счетными решениями ( PP ) и чередованием кванторов ( PH )1991 [статья 9]
1999Питер Шордля алгоритма Шора для факторизации чисел за полиномиальное время на квантовом компьютере1997 [статья 10]
2000Моше Ю. Варди и Пьер Вольперза работу по временной логике с конечными автоматами1994 [статья 11]
2001Санджив Арора , Уриэль Файги , Шафи Гольдвассер , Карстен Лунд , Ласло Ловас , Раджив Мотвани , Шмуэль Сафра , Мадху Судан и Марио Сегедидля теоремы PCP и ее приложений к трудности аппроксимации1996, [документ 12] 1998, [документ 13] 1998 [документ 14]
2002Жеро Сенизергза доказательство того , что эквивалентность детерминированных автоматов с магазином разрешима2001 [статья 15]
2003Йоав Фройнд и Роберт Шапиредля алгоритма AdaBoost в машинном обучении1997 [статья 16]
2004Морис Херлихи , Майкл Сакс , Нир Шавит и Фотиос Захароглуза приложения топологии к теории распределенных вычислений1999, [статья 17] 2000 [статья 18]
2005Нога Алон , Йоси Матиас и Марио Сегедиза их основополагающий вклад в алгоритмы потоковой передачи1999 [статья 19]
2006Маниндра Агравал , Нирадж Каял , Нитин Саксенадля теста простоты AKS2004 [статья 20]
2007Александр Разборов , Стивен Рудичдля естественных доказательств1997 [статья 21]
2008Дэниэл Спилман , Шан-Хуа Тэндля сглаженного анализа алгоритмов2004 [статья 22]
2009Омер Рейнгольд , Салил Вадхан , Ави Вигдерсондля зигзагообразного произведения графов и ненаправленной связности в логарифмическом пространстве2002, [статья 23] 2008 [статья 24]
2010Санджив Арора , Джозеф СБ Митчеллза их одновременное открытие полиномиальной по времени аппроксимационной схемы для евклидовой задачи коммивояжера1998, [статья 25] 1999 [статья 26]
2011Йохан Хостадза доказательство оптимальных результатов неаппроксимируемости для различных комбинаторных задач2001 [статья 27]
2012Элиас Куцупиас , Христос Пападимитриу , Ноам Нисан , Амир Ронен , Тим Рафгарден и Ива Тардосза создание основ алгоритмической теории игр [3]2009, [документ 28] 2002, [документ 29] 2001 [документ 30]
2013Дэн Боне , Мэтью К. Франклин и Антуан Жудля многостороннего обмена ключами Диффи–Хеллмана и схемы Боне–Франклина в криптографии [4]2003, [статья 31]

2004 [статья 32]

2014Рональд Феджин , Амнон Лотем  [ фр ] и Мони Наордля оптимальных алгоритмов агрегации для промежуточного программного обеспечения [5]2003, [статья 33]
2015Дэниэл Спилман , Шан-Хуа Тэнза серию статей о почти линейных по времени решениях Лапласа [6]

2011 [статья 34] 2013 [статья 35] 2014 [статья 36]

2016Стивен Брукс и Питер У. О'Хернза изобретение логики параллельного разделения2007, [статья 37] 2007 [статья 38]
2017 [2]Синтия Дворк , Фрэнк МакШерри , Кобби Ниссим и Адам Д. Смитза изобретение дифференциальной конфиденциальности2006 [статья 39]
2018 [7]Одед Регевдля ознакомления с проблемой обучения с ошибками2009 [статья 40]
2019 [8]Ирит Динурза ее новое доказательство теоремы PCP с помощью увеличения зазора2007 [статья 41]
2020 [9]Робин Мозер и Габор Тардосза конструктивное доказательство локальной леммы Ловаса2010 [статья 42]
2021 [10]Андрей Булатов, Цзинь-И Цай , Си Чэнь , Мартин Дайер и Дэвид Ричербиза работу по классификации сложности подсчета задач удовлетворения ограничений2013 [документ 43] 2013 [документ 44] 2017 [документ 45]
2022 [11]Звика Бракерски , Крэйг Джентри и Винод Вайкунтанатанза их преобразующий вклад в криптографию путем построения эффективных схем полностью гомоморфного шифрования (FHE)2014, [статья 46] 2014 [статья 47]
2023 [12]Сэмюэль Фиорини, Серж Массар и Себастьян Покутта, Ханс Радж Тивари, Рональд де Вольф и Томас Ротвоссза демонстрацию того, что любая расширенная формулировка для многогранника TSP имеет экспоненциальный размер2015, [статья 48] 2017 [статья 49]
2024 [13]Райан Уильямсза его работу по нижним границам схем и парадигме «алгоритмов для нижних границ»2011 [статья 50]

Победившие работы

  1. ^ Бабай, Ласло; Моран, Шломо (1988), «Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности» (PDF) , Журнал компьютерных и системных наук , 36 (2): 254–276, doi : 10.1016/0022-0000(88)90028-1 , ISSN  0022-0000
  2. ^ Голдвассер, С.; Микали, С.; Ракофф, К. (1989), «Сложность знаний интерактивных систем доказательства» (PDF) , SIAM Journal on Computing , 18 (1): 186–208, CiteSeerX 10.1.1.397.4002 , doi : 10.1137/0218012, ISSN  1095-7111 
  3. ^ Хастад, Йохан (1989), «Почти оптимальные нижние границы для схем малой глубины» (PDF) , в Микали, Сильвио (ред.), Случайность и вычисления , Достижения в области вычислительных исследований, т. 5, JAI Press, стр. 6–20, ISBN 978-0-89232-896-3, заархивировано из оригинала (PDF) 2012-02-22
  4. ^ Иммерман, Нил (1988), «Недетерминированное пространство замкнуто относительно дополнения» (PDF) , SIAM Journal on Computing , 17 (5): 935–938, CiteSeerX 10.1.1.54.5941 , doi :10.1137/0217058, ISSN  1095-7111 
  5. ^ Селепсени, Р. (1988), «Метод принудительного перебора недетерминированных автоматов» (PDF) , Acta Informatica , 26 (3): 279–284, doi : 10.1007/BF00299636, hdl : 10338.dmlcz/120489, S2CID  10838178
  6. ^ Синклер, А.; Джеррум, М. (1989), «Приблизительный подсчет, равномерная генерация и быстрое перемешивание цепей Маркова», Информация и вычисления , 82 (1): 93–133, doi : 10.1016/0890-5401(89)90067-9 , ISSN  0890-5401
  7. ^ Джеррум, М.; Синклер, Алистер (1989), «Аппроксимация постоянного», SIAM Journal on Computing , 18 (6): 1149–1178, CiteSeerX 10.1.1.431.4190 , doi : 10.1137/0218077, ISSN  1095-7111 
  8. ^ Халперн, Джозеф ; Моисей, Йорам (1990), «Знание и общее знание в распределенной среде» (PDF) , Журнал ACM , 37 (3): 549–587, arXiv : cs/0006009 , doi :10.1145/79147.79161, S2CID  52151232
  9. ^ Тода, Сейносукэ (1991), «PP is as hard as the polynomial-time иерархия» (PDF) , SIAM Journal on Computing , 20 (5): 865–877, CiteSeerX 10.1.1.121.1246 , doi :10.1137/0220053, ISSN  1095-7111, архивировано из оригинала (PDF) 2016-03-03 , извлечено 2010-06-08 
  10. ^ Шор, Питер В. (1997), «Алгоритмы полиномиального времени для разложения на простые множители и дискретных логарифмов на квантовом компьютере», SIAM Journal on Computing , 26 (5): 1484–1509, arXiv : quant-ph/9508027 , doi : 10.1137/S0097539795293172, ISSN  1095-7111, S2CID  2337707
  11. ^ Варди, Моше Й.; Вольпер, Пьер (1994), «Рассуждения о бесконечных вычислениях» (PDF) , Информация и вычисления , 115 (1): 1–37, doi :10.1006/inco.1994.1092, ISSN  0890-5401, архивировано из оригинала (PDF) 25.08.2011
  12. ^ Фейге, Уриэль; Голдвассер, Шафи; Ловас, Ласло; Сафра, Шмуэль; Сегеди, Марио (1996), «Интерактивные доказательства и сложность аппроксимации клик» (PDF) , Журнал ACM , 43 (2): 268–292, doi : 10.1145/226643.226652 , ISSN  0004-5411
  13. ^ Арора, Санджив; Сафра, Шмуэль (1998), «Вероятностная проверка доказательств: новая характеристика NP» (PDF) , Журнал ACM , 45 (1): 70–122, doi :10.1145/273865.273901, ISSN  0004-5411, S2CID  751563, архивировано из оригинала (PDF) 2011-06-10
  14. ^ Арора, Санджив; Лунд, Карстен; Мотвани, Раджив; Судан, Мадху; Сегеди, Марио (1998), «Проверка доказательств и сложность задач аппроксимации» (PDF) , Журнал ACM , 45 (3): 501–555, CiteSeerX 10.1.1.145.4652 , doi :10.1145/278298.278306, ISSN  0004-5411, S2CID  8561542, архивировано из оригинала (PDF) 2011-06-10 
  15. ^ Сенизерг, Жеро (2001), «L(A) = L(B)? разрешимость следует из полных формальных систем», Теор. комп. наук , 251 (1): 1–166, doi :10.1016/S0304-3975(00)00285-1, ISSN  0304-3975
  16. ^ Фройнд, Й.; Шапир, Р. Э. (1997), «Обобщение теории принятия решений для онлайн-обучения и его применение для повышения эффективности» (PDF) , Журнал компьютерных и системных наук , 55 (1): 119–139, doi :10.1006/jcss.1997.1504, ISSN  1090-2724
  17. ^ Херлихи, Морис ; Шавит, Нир (1999), «Топологическая структура асинхронной вычислимости» (PDF) , Журнал ACM , 46 (6): 858–923, CiteSeerX 10.1.1.78.1455 , doi :10.1145/331524.331529, S2CID  5797174 . Лекция о премии Гёделя
  18. ^ Сакс, Майкл ; Захароглу, Фотиос (2000), «Соглашение о k -множестве без ожидания невозможно: топология общедоступных знаний», SIAM Journal on Computing , 29 (5): 1449–1483, doi :10.1137/S0097539796307698
  19. ^ Алон, Нога ; Матиас, Йосси; Сегеди, Марио (1999), «Пространственная сложность аппроксимации частотных моментов» (PDF) , Журнал компьютерных и системных наук , 58 (1): 137–147, doi :10.1006/jcss.1997.1545. Впервые представлен на Симпозиуме по теории вычислений (STOC) в 1996 году.
  20. ^ Агравал, М.; Каял, Н.; Саксена, Н. (2004), «PRIMES is in P», Annals of Mathematics , 160 (2): 781–793, doi : 10.4007/annals.2004.160.781 , ISSN  0003-486X
  21. ^ Разборов, Александр А.; Рудич, Стивен (1997), «Естественные доказательства», Журнал компьютерных и системных наук , 55 (1): 24–35, doi : 10.1006/jcss.1997.1494 , ISSN  0022-0000, ECCC  TR94-010
  22. ^ Шпильман, Дэниел А.; Тенг, Шан-Хуа (2004), «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время», J. ACM , 51 (3): 385–463, arXiv : math/0212413 , doi : 10.1145/990308.990310, ISSN  0004-5411
  23. ^ Рейнгольд, Омер; Вадхан, Салил; Вигдерсон, Ави (2002), «Волны энтропии, произведение зигзагообразных графов и новые расширители постоянной степени», Annals of Mathematics , 155 (1): 157–187, CiteSeerX 10.1.1.236.8669 , doi :10.2307/3062153, ISSN  0003-486X, JSTOR  3062153, MR  1888797, S2CID  120739405 
  24. ^ Рейнгольд, Омер (2008), «Ненаправленная связность в лог-пространстве», J. ACM , 55 (4): 1–24, doi : 10.1145/1391289.1391291, ISSN  0004-5411, S2CID  207168478[ постоянная мертвая ссылка ‍ ]
  25. ^ Арора, Санджив (1998), «Схемы полиномиального времени аппроксимации для евклидовых коммивояжеров и других геометрических задач», Журнал ACM , 45 (5): 753–782, CiteSeerX 10.1.1.23.6765 , doi :10.1145/290179.290180, ISSN  0004-5411, S2CID  3023351 
  26. ^ Митчелл, Джозеф СБ (1999), «Подразделения гильотины приближают многоугольные подразделения: простая схема аппроксимации за полиномиальное время для геометрических задач коммивояжера, k-MST и связанных с ними задач», SIAM Journal on Computing , 28 (4): 1298–1309, doi :10.1137/S0097539796309764, ISSN  1095-7111
  27. ^ Хастад, Йохан (2001), «Некоторые оптимальные результаты неаппроксимируемости» (PDF) , Журнал ACM , 48 (4): 798–859, CiteSeerX 10.1.1.638.2808 , doi :10.1145/502090.502098, ISSN  0004-5411, S2CID  5120748 
  28. ^ Куцупиас, Элиас; Пападимитриу, Христос (2009). «Наихудшее равновесие». Обзор компьютерных наук . 3 (2): 65–69. doi :10.1016/j.cosrev.2009.04.003.
  29. ^ Рафгарден, Тим; Тардос, Ива (2002). «Насколько плоха эгоистичная маршрутизация?». Журнал ACM . 49 (2): 236–259. CiteSeerX 10.1.1.147.1081 . doi :10.1145/506147.506153. S2CID  207638789. 
  30. ^ Нисан, Ноам; Ронен, Амир (2001). «Проектирование алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. CiteSeerX 10.1.1.21.1731 . doi :10.1006/game.1999.0790. 
  31. ^ Бонех, Дэн; Франклин, Мэтью (2003). «Шифрование на основе идентификации из спаривания Вейля». SIAM Journal on Computing . 32 (3): 586–615. CiteSeerX 10.1.1.66.1131 . doi :10.1137/S0097539701398521. MR  2001745. 
  32. ^ Жу, Антуан (2004). «Протокол одного раунда для трехстороннего протокола Диффи-Хеллмана». Журнал криптологии . 17 (4): 263–276. doi : 10.1007/s00145-004-0312-y . MR  2090557. S2CID  3350730.
  33. ^ Фагин, Рональд; Лотем, Амнон; Наор, Мони (2003). «Оптимальные алгоритмы агрегации для промежуточного программного обеспечения». Журнал компьютерных и системных наук . 66 (4): 614–656. arXiv : cs/0204046 . doi :10.1016/S0022-0000(03)00026-6.
  34. ^ Шпильман, Дэниел А.; Тенг, Шан-Хуа (2011). «Спектральное разрежение графов». SIAM Journal on Computing . 40 (4): 981–1025. arXiv : 0808.4134 . doi : 10.1137/08074489X. ISSN  0097-5397. S2CID  9646279.
  35. ^ Шпильман, Дэниел А.; Тенг, Шан-Хуа (2013). «Локальный алгоритм кластеризации для массивных графов и его применение для разбиения графов за почти линейное время». SIAM Journal on Computing . 42 (1): 1–26. arXiv : 0809.3232 . doi : 10.1137/080744888. ISSN  0097-5397. S2CID  9151077.
  36. ^ Шпильман, Дэниел А.; Тенг, Шан-Хуа (2014). «Почти линейные по времени алгоритмы для предварительной подготовки и решения симметричных диагонально доминирующих линейных систем». Журнал SIAM по матричному анализу и приложениям . 35 (3): 835–885. arXiv : cs/0607105 . doi :10.1137/090771430. ISSN  0895-4798. S2CID  1750944.
  37. ^ Брукс, Стивен (2007). «Семантика для логики параллельного разделения» (PDF) . Теоретическая информатика . 375 (1–3): 227–270. doi :10.1016/j.tcs.2006.12.034.
  38. ^ О'Херн, Питер (2007). «Ресурсы, параллелизм и локальные рассуждения» (PDF) . Теоретическая информатика . 375 (1–3): 271–307. doi : 10.1016/j.tcs.2006.12.035 .
  39. ^ Дворк, Синтия; Макшерри, Фрэнк; Ниссим, Кобби; Смит, Адам (2006). Халеви, Шай; Рабин, Тал (ред.). Калибровка шума по чувствительности в анализе частных данных . Теория криптографии (TCC). Конспект лекций по информатике. Том 3876. Springer-Verlag. С. 265–284. doi : 10.1007/11681878_14 . ISBN 978-3-540-32731-8.
  40. ^ Регев, Одед (2009). «О решетках, обучении с ошибками, случайных линейных кодах и криптографии». Журнал ACM . 56 (6): 1–40. CiteSeerX 10.1.1.215.3543 . doi :10.1145/1568318.1568324. S2CID  207156623. 
  41. ^ Динур, Ирит (2007). «Теорема PCP об усилении разрыва». Журнал АКМ . 54 (3): 12–с. дои : 10.1145/1236457.1236459. S2CID  53244523.
  42. ^ "Конструктивное доказательство общей локальной леммы Ловаса". Журнал ACM . 57 (2). 2010. doi :10.1145/1667053. ISSN  0004-5411.
  43. ^ Булатов, Андрей А. (2013). «Сложность проблемы удовлетворения ограничений подсчета». Журнал ACM . 60 (5). Ассоциация вычислительной техники: 1–41. doi : 10.1145/2528400. ISSN  0004-5411. S2CID  8964233.
  44. ^ Дайер, Мартин; Ричерби, Дэвид (2013). «Эффективная дихотомия для проблемы удовлетворения ограничений подсчета». Журнал SIAM по вычислениям . 42 (3). Общество промышленной и прикладной математики (SIAM): 1245–1274. arXiv : 1003.3879 . doi : 10.1137/100811258. ISSN  0097-5397. S2CID  1247279.
  45. ^ Cai, Jin-Yi; Chen, Xi (2017-06-22). «Сложность подсчета CSP с комплексными весами». Журнал ACM . 64 (3). Ассоциация вычислительной техники: 1–39. arXiv : 1111.2384 . doi : 10.1145/2822891. ISSN  0004-5411. S2CID  1053684.
  46. ^ Бракерски, Звика; Вайкунтанатан, Винод (январь 2014 г.). «Эффективное полностью гомоморфное шифрование из (стандартного) $\mathsf{LWE}$». SIAM Journal по вычислительной технике . 43 (2): 831–871. дои : 10.1137/120868669. hdl : 1721.1/115488 . ISSN  0097-5397. S2CID  8831240.
  47. ^ Brakerski, Zvika; Gentry, Craig; Vaikuntanathan, Vinod (2012). "(Уровневое) полностью гомоморфное шифрование без самонастройки". Труды 3-й конференции по инновациям в теоретической информатике . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 309–325. doi :10.1145/2090236.2090262. ISBN 9781450311151. S2CID  2602543.
  48. ^ Фиорини, Самуэль; Массар, Серж; Покутта, Себастьян; Тивари, Ханс Радж; де Вольф, Рональд (2015). «Экспоненциальные нижние границы для многогранников в комбинаторной оптимизации». Журнал АКМ . 62 (2): 17:1–17:23. arXiv : 1111.0837 . дои : 10.1145/2716307. S2CID  7372000.
  49. ^ Ротвосс, Томас (2017). «Соответствующий многогранник имеет экспоненциальную сложность расширения». Журнал ACM . 64 (6): 41:1–41:19. arXiv : 1311.2369 . doi : 10.1145/3127497. S2CID  47045361.
  50. ^ Уильямс, Райан (июнь 2011 г.). «Нижние границы неоднородных цепей ACC». 2011 IEEE 26-я ежегодная конференция по вычислительной сложности . IEEE. стр. 115–125. doi :10.1109/ccc.2011.36. ISBN 978-1-4577-0179-5.

Смотрите также

Примечания

  1. ^ «Письмо Гёделя». 2009-02-12.
  2. ^ ab "Премия Гёделя 2017 года". Европейская ассоциация теоретической информатики . EATCS . ​​Получено 29 марта 2017 г.
  3. ^ "Три статьи, цитируемые для заложения фундамента роста в алгоритмической теории игр". 16 мая 2012 г. Архивировано из оригинала 18 июля 2013 г. Получено 16 мая 2012 г.
  4. ^ ACM Group вручает премию Гёделя за достижения в области криптографии: три учёных-компьютерщика отмечены за инновации, повышающие безопасность. Архивировано 01.06.2013 на Wayback Machine , Ассоциация вычислительной техники , 29 мая 2013 г.
  5. ^ Получатели достигли новаторских результатов в агрегации данных из нескольких источников, Ассоциация вычислительной техники , 30 апреля 2014 г.
  6. ↑ Объявление о присуждении премии Гёделя 2015 г. Архивировано 09.12.2017 г. на Wayback Machine Ассоциацией вычислительной техники .
  7. ^ "Цитата о премии Гёделя 2018 года".
  8. ^ "Цитата о премии Гёделя 2019 года".
  9. ^ "Цитата о премии Гёделя 2020 года".
  10. ^ "Цитата о премии Гёделя 2021 года".
  11. ^ "Цитата о премии Гёделя 2022 года".
  12. ^ "Цитата о премии Гёделя 2023 года".
  13. ^ "Цитата о награждении премией Гёделя 2024 года".

Ссылки

  • Сайт премии со списком победителей
Взято с "https://en.wikipedia.org/w/index.php?title=Gödel_Prize&oldid=1239821267"