Премия Гёделя
Из Википедии, бесплатной энциклопедии
  (Перенаправлено с премии Гёделя )
Перейти к навигации Перейти к поиску
Не путать с лекцией Гёделя .

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

Премия Гёделя вручается с 1993 года. Премия присуждается либо на STOC ( Симпозиум ACM по теории вычислений , одна из основных североамериканских конференций по теоретической информатике), либо на ICALP ( Международный коллоквиум по автоматам, языкам и программированию , один из основные европейские конференции в этой области). Чтобы иметь право на получение приза, статья должна быть опубликована в рецензируемом журнале в течение последних 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 г.Géraud Sénizerguesдля доказательства того, что эквивалентность детерминированных магазинных автоматов является разрешимой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 г.Санджив Арора , Джозеф С.Б. Митчеллза их одновременное открытие схемы полиномиального приближения (PTAS) для евклидовой задачи коммивояжера (ETSP)1998, [статья 25]

1999 [статья 26]

2011 г.Йохан Хастаддля доказательства оптимальных результатов о приближаемости различных комбинаторных задач2001 [статья 27]
2012 г.Элиас Koutsoupias , Пападимитий , Ноам Нисан , Амир Ронен  [ де ] , Тим Роугарден и Эва Тардосдля создания основ алгоритмической теории игр [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]Робин Мозер и Габор Тардосдля их конструктивного доказательства в локальной леммы Lovász2010 [статья 42]
2021 [10]Андрей Булатов, Цзинь-И Цай, Си Чен, Мартин Дайер и Дэвид Ричербиза их работу по классификации подсчета сложности из проблем удовлетворения ограничений2013 [статья 43]

2013 [документ 44] 2017 [документ 45]

Выигрышные документы

  1. ^ Бабай, Ласло; Moran, Шломо (1988), "Артур-Мерлин игры: рандомизированное стойкую систему и иерархию класса сложности" (PDF) , Журнал вычислительной техники и системы наук , 36 (2): 254-276, DOI : 10.1016 / 0022 -0000 (88) 90028-1 , ISSN  0022-0000
  2. ^ Goldwasser, S .; Micali, S .; Rackoff, C. (1989), "Сложность знание интерактивных систем доказательств" (PDF) , SIAM журнал по вычислениям , 18 (1): 186-208, CiteSeerX 10.1.1.397.4002 , DOI : 10,1137 / 0218012 , ISSN 1095 -7111   
  3. ^ Håstad, Йохан (1989), "Почти Оптимальное нижние границы для малых глубины схем" (PDF) , в Микали, Сильвио (ред.), Случайность и Исчисление , Успехи в компьютерных исследований, 5 , JAI Press, стр. 6-20 , ISBN  978-0-89232-896-3, архивировано из оригинального (PDF) 22.02.2012
  4. ^ Иммерман, Нил (1988), "Недетерминированные пространство закрыто под дополнительности" (PDF) , SIAM журнал по вычислениям , 17 (5): 935-938, CiteSeerX 10.1.1.54.5941 , DOI : 10,1137 / 0217058 , ISSN 1095- 7111   
  5. ^ Szelepcsenyi, R. (1988), "Метод принудительного перечисления для недетерминированных автоматов" (PDF) , Acta Informatica , 26 (3): 279-284, DOI : 10.1007 / BF00299636 , ЛВП : 10338.dmlcz / 120489 , S2CID 10838178  
  6. ^ Sinclair, A .; Jerrum, М. (1989), "Приближенный подсчет, равномерное формирование и быстрое смешивание цепей Маркова", информационные и вычислительные , 82 (1): 93-133, DOI : 10,1016 / 0890-5401 (89) 90067-9 , ISSN 0890 -5401 
  7. ^ Jerrum, M .; Sinclair, Алистер (1989), "Аппроксимация постоянный", SIAM журнал по вычислениям , 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. ^ Тода, Seinosuke (1991), "ПП так сложно , как иерархии полиномиальной" (PDF) , SIAM журнал по вычислениям , 20 (5): 865-877, CiteSeerX 10.1.1.121.1246 , DOI : 10,1137 / 0220053 , ISSN 1095-7111   
  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) на 2011-08-25  
  12. ^ Файги, Уриэль; Гольдвассер, Шафи; Ловас, Ласло; Сафра, Шмуэль; Szegedy, Марио (1996), "Интерактивные доказательства и твердость аппроксимирующих кликов" (PDF) , Журнал ACM , 43 (2): 268-292, DOI : 10,1145 / 226643,226652 , ISSN 0004-5411  
  13. ^ Арора, Санджив; Сафра, Шмуэль (1998), "Вероятностная проверка доказательств: новая характеристика НП" (PDF) , Журнал ACM , 45 (1): 70-122, DOI : 10,1145 / 273865,273901 , ISSN 0004-5411 , S2CID 751563 , архивировано из оригинального (PDF) 10.06.2011   
  14. ^ Арора, Санджив; Лунд, Карстен; Мотвани, Раджив; Судан, Мадху; Szegedy, Марио (1998), "Доказательство проверка и твердость задач аппроксимации" (PDF) , Журнал ACM , 45 (3): 501-555, CiteSeerX 10.1.1.145.4652 , DOI : 10,1145 / 278298,278306 , ISSN 0004 -5411 , S2CID 8561542 , архивировано из оригинала (PDF) 10.06.2011    
  15. ^ Sénizergues, Géraud (2001), «L (A) = L (B)? Разрешимость вытекает из полных формальных систем», Theor. Comput. Sci. , 251 (1): 1-166, DOI : 10.1016 / S0304-3975 (00) 00285-1 , ISSN 0304-3975 
  16. ^ Freund, Y .; Schapire, RE (1997), «Теоретико-решающее обобщение онлайн-обучения и приложение для повышения квалификации» (PDF) , Journal of Computer and System Sciences , 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. ^ Agrawal, M .; Kayal, N .; Саксена, Н. (2004), "PRIMES в Р", Анналы математики , 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. ^ Spielman, Daniel A .; Тэн, Шан-Хуа (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. ^ Arora, Санджив (1998), " О полиномиальных схем времени аппроксимации для евклидовой коммивояжера и других геометрических задач", Журнал ACM , 45 (5): 753-782, CiteSeerX 10.1.1.23.6765 , DOI : 10,1145 / 290179,290180 , ISSN 0004-5411 , S2CID 3023351   
  26. ^ Митчелл, Джозеф С.Б. (1999), «Гильотинные подразделения, приближенные многоугольные подразделения: простая схема аппроксимации полиномиальным временем для геометрического TSP, k-MST и связанных проблем», SIAM Journal on Computing , 28 (4): 1298–1309, DOI : 10,1137 / S0097539796309764 , ISSN 1095-7111 
  27. ^ Håstad, Йохан (2001), "Некоторые результаты оптимальной inapproximability" (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. ^ Roughgarden, Тим; Тардос, Ева (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 . Руководство по ремонту 2001745 .  
  32. ^ Жу, Антуан (2004). «Протокол одного раунда для трехстороннего Диффи-Хеллмана». Журнал криптологии . 17 (4): 263–276. DOI : 10.1007 / s00145-004-0312-у . Руководство по ремонту 2090557 . S2CID 3350730 .  
  33. ^ Феджин, Рональд; Лотем, Амнон; Наор, Мони (2003). «Оптимальные алгоритмы агрегирования для промежуточного программного обеспечения». Журнал компьютерных и системных наук . 66 (4): 614–656. arXiv : cs / 0204046 . DOI : 10.1016 / S0022-0000 (03) 00026-6 .
  34. ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2011). «Спектральное разрежение графов». SIAM Journal on Computing . 40 (4): 981–1025. arXiv : 0808.4134 . DOI : 10.1137 / 08074489X . ISSN 0097-5397 . S2CID 9646279 .  
  35. ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2013). «Алгоритм локальной кластеризации для массивных графов и его применение для разбиения почти линейного временного графа». SIAM Journal on Computing . 42 (1): 1-26. arXiv : 0809.3232 . DOI : 10.1137 / 080744888 . ISSN 0097-5397 . S2CID 9151077 .  
  36. ^ Spielman, Daniel A .; Тэн, Шан-Хуа (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. ^ O'Hearn, Питер (2007). «Ресурсы, параллелизм и локальное мышление» (PDF) . Теоретическая информатика . 375 (1–3): 271–307. DOI : 10.1016 / j.tcs.2006.12.035 .
  39. ^ Дворк, Синтия; Макшерри, Фрэнк; Ниссим, Кобби; Смит, Адам (2006). Халеви, Шай; Рабин, Тал (ред.). Калибровка шума по чувствительности при анализе частных данных . Теория криптографии (ТСС). Конспект лекций по информатике. 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 по усилению разрыва» . Журнал ACM . 54 (3): 12 – es. DOI : 10.1145 / 1236457.1236459 . S2CID 53244523 . 
  42. ^ "Конструктивное доказательство общей локальной леммы Ловаса". Журнал ACM . 57 (2). 2010. DOI : 10,1145 / 1667053 . ISSN 0004-5411 . 
  43. ^ Булатов, Андрей А. (2013). «Сложность проблемы удовлетворения ограничений подсчета». Журнал ACM . Ассоциация вычислительной техники (ACM). 60 (5): 1–41. DOI : 10.1145 / 2528400 . ISSN 0004-5411 . S2CID 8964233 .  
  44. ^ Дайер, Мартин; Ричерби, Дэвид (2013). «Эффективная дихотомия для проблемы удовлетворения ограничения подсчета». SIAM Journal on Computing . Общество промышленной и прикладной математики (SIAM). 42 (3): 1245–1274. arXiv : 1003,3879 . DOI : 10.1137 / 100811258 . ISSN 0097-5397 . S2CID 1247279 .  
  45. ^ Цай, Цзинь-И; Чен, Си (2017-06-22). «Сложность подсчета CSP с комплексными весами». Журнал ACM . Ассоциация вычислительной техники (ACM). 64 (3): 1–39. arXiv : 1111.2384 . DOI : 10.1145 / 2822891 . ISSN 0004-5411 . S2CID 1053684 .  

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

  • Список наград в области информатики

Примечания

  1. ^ "Письмо Гёделя" . 2009-02-12.
  2. ^ a b «Премия Гёделя 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 Гедель премия объявления Архивировано 2017-12-09 в Wayback Machine по Ассоциации вычислительной техники .
  7. ^ «Цитирование премии Гёделя 2018» .
  8. ^ "Цитирование Премии Гёделя 2019" .
  9. ^ «Цитирование Премии Гёделя 2020» .
  10. ^ «Цитирование премии Гёделя 2021 года» .

использованная литература

  • Сайт приза со списком победителей
Источник « https://en.wikipedia.org/w/index.php?title=Gödel_Prize&oldid=1054522530 »
Contribute a better translation