Премия Гёделя - это ежегодная премия за выдающиеся работы в области теоретической информатики , присуждаемая совместно Европейской ассоциацией теоретических компьютерных наук (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 г. | Маниндра Агравал , Нирадж Каял , Нитин Саксена | для теста простоты AKS | 2004 [статья 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ász | 2010 [статья 42] | |
2021 [10] | Андрей Булатов, Цзинь-И Цай, Си Чен, Мартин Дайер и Дэвид Ричерби | за их работу по классификации подсчета сложности из проблем удовлетворения ограничений | 2013 [статья 43] 2013 [документ 44] 2017 [документ 45] |
Выигрышные документы
- ^ Бабай, Ласло; Moran, Шломо (1988), "Артур-Мерлин игры: рандомизированное стойкую систему и иерархию класса сложности" (PDF) , Журнал вычислительной техники и системы наук , 36 (2): 254-276, DOI : 10.1016 / 0022 -0000 (88) 90028-1 , ISSN 0022-0000
- ^ 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
- ^ Хастад, Йохан (1989), «Почти оптимальные нижние границы для схем малой глубины» (PDF) , в Микали, Сильвио (ред.), Случайность и вычисления , Достижения в компьютерных исследованиях, 5 , JAI Press, стр. 6–20, ISBN 978-0-89232-896-3, архивировано из оригинального (PDF) 22.02.2012
- ^ Иммерман, Нил (1988), "Недетерминированные пространство закрыто под дополнительности" (PDF) , SIAM журнал по вычислениям , 17 (5): 935-938, CiteSeerX 10.1.1.54.5941 , DOI : 10,1137 / 0217058 , ISSN 1095-7111
- ^ Szelepcsenyi, Р. (1988), "Метод принудительного перечисления для недетерминированных автоматов" (PDF) , Acta Informatica , 26 (3): 279-284, DOI : 10.1007 / BF00299636 , ЛВП : 10338.dmlcz / 120489 , S2CID 10838178
- ^ Sinclair, A .; Jerrum, М. (1989), "Приближенный подсчет, равномерное формирование и быстрое смешивание цепей Маркова", информационные и вычислительные , 82 (1): 93-133, DOI : 10,1016 / 0890-5401 (89) 90067-9 , ISSN 0890 -5401
- ^ Jerrum, M .; Sinclair, Алистер (1989), "Аппроксимация постоянный", SIAM журнал по вычислениям , 18 (6): 1149-1178, CiteSeerX 10.1.1.431.4190 , DOI : 10,1137 / 0218077 , ISSN 1095-7111
- ^ Халперн, Джозеф ; Моисей, Йорам (1990), «Знания и общие знания в распределенной среде» (PDF) , Журнал ACM , 37 (3): 549–587, arXiv : cs / 0006009 , doi : 10.1145 / 79147.79161 , S2CID 52151232
- ^ Тода, Сейноскэ (1991), «PP так же сложен, как иерархия полиномиального времени» (PDF) , SIAM Journal on Computing , 20 (5): 865–877, CiteSeerX 10.1.1.121.1246 , doi : 10.1137 / 0220053 , ISSN 1095-7111
- ^ Шор, Питер У. (1997), «Полиномиальные алгоритмы для простой факторизации и дискретных логарифмов на квантовом компьютере» (PDF) , SIAM Journal on Computing , 26 (5): 1484–1509, arXiv : Quant-ph / 9508027 , DOI : 10.1137 / S0097539795293172 , ISSN 1095-7111 , S2CID 2337707[ постоянная мертвая ссылка ]
- ^ Варди, Моше Й .; Вольпер, Пьер (1994), "Рассуждения о бесконечных вычислениях" (PDF) , Информация и вычисления , 115 (1): 1–37, DOI : 10.1006 / inco.1994.1092 , ISSN 0890-5401 , заархивировано из оригинала (PDF) на 2011-08-25
- ^ Файги, Уриэль; Гольдвассер, Шафи; Ловас, Ласло; Сафра, Шмуэль; Szegedy, Марио (1996), "Интерактивные доказательства и твердость аппроксимирующих кликов" (PDF) , Журнал ACM , 43 (2): 268-292, DOI : 10,1145 / 226643,226652 , ISSN 0004-5411
- ^ Арора, Санджив; Сафра, Шмуэль (1998), "Вероятностная проверка доказательств: новая характеристика НП" (PDF) , Журнал ACM , 45 (1): 70-122, DOI : 10,1145 / 273865,273901 , ISSN 0004-5411 , S2CID 751563 , архивировано из оригинального (PDF) 10.06.2011
- ^ Арора, Санджив; Лунд, Карстен; Мотвани, Раджив; Судан, Мадху; 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
- ^ Sénizergues, Géraud (2001), "L (A) = L (B) - разрешимость результатов из полных формальных систем", Теор. Comput. Sci. , 251 (1): 1-166, DOI : 10.1016 / S0304-3975 (00) 00285-1 , ISSN 0304-3975
- ^ 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
- ^ Херлихи, Морис ; Шавит, Нир (1999), "О топологической структуре асинхронной вычислимости" (PDF) , Журнал ACM , 46 (6): 858-923, CiteSeerX 10.1.1.78.1455 , DOI : 10,1145 / 331524,331529 , S2CID 5797174. Лекция о премии Гёделя
- ^ Сакс, Майкл ; Захароглу, Фотиос (2000), « Соглашение о k- множестве без ожидания невозможно: топология общедоступных знаний», SIAM Journal on Computing , 29 (5): 1449–1483, DOI : 10.1137 / S0097539796307698
- ^ Алон, Нога ; Матиас, Йосси; Сегеди, Марио (1999), «Пространственная сложность аппроксимации частотных моментов» (PDF) , Журнал компьютерных и системных наук , 58 (1): 137–147, DOI : 10.1006 / jcss.1997.1545. Впервые представлен на симпозиуме по теории вычислений (STOC) в 1996 году.
- ^ Agrawal, M .; Kayal, N .; Саксена, Н. (2004), "PRIMES в Р", Анналы математики , 160 (2): 781-793, DOI : 10,4007 / annals.2004.160.781 , ISSN 0003-486X
- ^ Разборов Александр А .; Рудич, Стивен (1997), "Природные доказательства", журнал компьютерных и системных наук , 55 (1): 24-35, DOI : 10,1006 / jcss.1997.1494 , ISSN 0022-0000 , ECCC TR94-010
- ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2004), «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно требует полиномиального времени» (PDF) , J. ACM , 51 (3): 385–463, arXiv : math / 0212413 , doi : 10.1145 /990308.990310 , ISSN 0004-5411[ постоянная мертвая ссылка ]
- ^ Рейнгольд, Омер; Вадхан, Салил; Вигдерсон, Ави (2002), «Энтропийные волны, зигзагообразное графическое произведение и новые расширители постоянной степени» (PDF) , 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[ постоянная мертвая ссылка ]
- ^ Рейнгольд, Омер (2008), "неориентированный подключения в лог-пространстве" , J. ACM , 55 (4): 1-24, DOI : 10,1145 / 1391289,1391291 , ISSN 0004-5411 , S2CID 207168478[ постоянная мертвая ссылка ]
- ^ Арора, Санджив (1998), " О полиномиальных схем времени аппроксимации для евклидовой коммивояжера и других геометрических задач", Журнал ACM , 45 (5): 753-782, CiteSeerX 10.1.1.23.6765 , DOI : 10,1145 / 290179,290180 , ISSN 0004-5411 , S2CID 3023351
- ^ Митчелл, Джозеф С.Б. (1999), «Гильотинные подразделения, приближенные многоугольные подразделения: простая схема аппроксимации полиномиальным временем для геометрического TSP, k-MST и связанных проблем», SIAM Journal on Computing , 28 (4): 1298–1309, doi : 10.1137 / S0097539796309764 , ISSN 1095-7111
- ^ 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
- ^ Кутсупиас, Элиас; Пападимитриу, Христос (2009). «Худшее равновесие». Обзор компьютерных наук . 3 (2): 65–69. DOI : 10.1016 / j.cosrev.2009.04.003 .
- ^ Roughgarden, Тим; Тардос, Ева (2002). «Насколько плоха эгоистичная маршрутизация?». Журнал ACM . 49 (2): 236–259. CiteSeerX 10.1.1.147.1081 . DOI : 10.1145 / 506147.506153 . S2CID 207638789 .
- ^ Нисан, Ноам; Ронен, Амир (2001). «Разработка алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. CiteSeerX 10.1.1.21.1731 . DOI : 10,1006 / game.1999.0790 .
- ^ Бонех, Дэн; Франклин, Мэтью (2003). «Шифрование на основе личности из пары Вейля». SIAM Journal on Computing . 32 (3): 586–615. CiteSeerX 10.1.1.66.1131 . DOI : 10,1137 / S0097539701398521 . Руководство по ремонту 2001745 .
- ^ Жу, Антуан (2004). «Протокол одного раунда для трехстороннего Диффи-Хеллмана». Журнал криптологии . 17 (4): 263–276. DOI : 10.1007 / s00145-004-0312-у . Руководство по ремонту 2090557 . S2CID 3350730 .
- ^ Феджин, Рональд; Лотем, Амнон; Наор, Мони (2003). «Оптимальные алгоритмы агрегирования для промежуточного программного обеспечения». Журнал компьютерных и системных наук . 66 (4): 614–656. arXiv : cs / 0204046 . DOI : 10.1016 / S0022-0000 (03) 00026-6 .
- ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2011). «Спектральное разрежение графов». SIAM Journal on Computing . 40 (4): 981–1025. arXiv : 0808.4134 . DOI : 10.1137 / 08074489X . ISSN 0097-5397 . S2CID 9646279 .
- ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2013). «Алгоритм локальной кластеризации для массивных графов и его применение для разбиения почти линейного временного графа». SIAM Journal on Computing . 42 (1): 1-26. arXiv : 0809.3232 . DOI : 10.1137 / 080744888 . ISSN 0097-5397 . S2CID 9151077 .
- ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2014). «Алгоритмы, близкие к линейному времени для предварительной подготовки и решения симметричных, диагонально доминирующих линейных систем». Журнал SIAM по матричному анализу и приложениям . 35 (3): 835–885. arXiv : cs / 0607105 . DOI : 10.1137 / 090771430 . ISSN 0895-4798 . S2CID 1750944 .
- ^ Брукс, Стивен (2007). «Семантика для логики параллельного разделения» (PDF) . Теоретическая информатика . 375 (1–3): 227–270. DOI : 10.1016 / j.tcs.2006.12.034 .
- ^ О'Хирн, Питер (2007). «Ресурсы, параллелизм и локальное мышление» (PDF) . Теоретическая информатика . 375 (1–3): 271–307. DOI : 10.1016 / j.tcs.2006.12.035 .
- ^ Дворк, Синтия; Макшерри, Фрэнк; Ниссим, Кобби; Смит, Адам (2006). Халеви, Шай; Рабин, Тал (ред.). Калибровка шума по чувствительности при анализе частных данных . Теория криптографии (ТСС). Конспект лекций по информатике. 3876 . Springer-Verlag. С. 265–284. DOI : 10.1007 / 11681878_14 . ISBN 978-3-540-32731-8.
- ^ Регев, Одед (2009). «На решетках, обучение с ошибками, случайные линейные коды и криптография». Журнал ACM . 56 (6): 1–40. CiteSeerX 10.1.1.215.3543 . DOI : 10.1145 / 1568318.1568324 . S2CID 207156623 .
- ^ Динур, Ирит (2007). «Теорема PCP по усилению разрыва» . Журнал ACM . 54 (3): 12 – es. DOI : 10.1145 / 1236457.1236459 . S2CID 53244523 .
- ^ «Конструктивное доказательство общей локальной леммы Ловаса». Журнал ACM . 57 (2). 2010. DOI : 10,1145 / 1667053 . ISSN 0004-5411 .
- ^ Булатов, Андрей А. (2013). «Сложность проблемы удовлетворения ограничений подсчета». Журнал ACM . Ассоциация вычислительной техники (ACM). 60 (5): 1–41. DOI : 10.1145 / 2528400 . ISSN 0004-5411 . S2CID 8964233 .
- ^ Дайер, Мартин; Ричерби, Дэвид (2013). «Эффективная дихотомия для проблемы удовлетворения ограничения подсчета». SIAM Journal on Computing . Общество промышленной и прикладной математики (SIAM). 42 (3): 1245–1274. arXiv : 1003,3879 . DOI : 10.1137 / 100811258 . ISSN 0097-5397 . S2CID 1247279 .
- ^ Цай, Цзинь-И; Чен, Си (2017-06-22). «Сложность подсчета CSP с комплексными весами». Журнал ACM . Ассоциация вычислительной техники (ACM). 64 (3): 1–39. arXiv : 1111.2384 . DOI : 10.1145 / 2822891 . ISSN 0004-5411 . S2CID 1053684 .
Смотрите также
- Список наград в области информатики
Заметки
- ^ «Письмо Гёделя» . 2009-02-12.
- ^ а б «Премия Гёделя 2017 года» . Европейская ассоциация теоретической информатики . EATCS . Проверено 29 марта 2017 года .
- ^ «Три статьи, заложенные в основу развития теории алгоритмических игр» . 16 мая 2012 года Архивировано из оригинала 18 июля 2013 года . Проверено 16 мая 2012 года .
- ^ ACM Group представляет премию Гёделя за достижения в области криптографии: три компьютерных ученых, упомянутые за инновации, улучшающие безопасность Архивировано 01.06.2013 в Wayback Machine , Ассоциация вычислительной техники , 29 мая 2013 г.
- ^ Получатели достигли революционных результатов в агрегировании данных из нескольких источников , Ассоциация вычислительной техники , 30 апреля 2014 г.
- ^ 2015 Гедель премия объявления Архивировано 2017-12-09 в Wayback Machine по Ассоциации вычислительной техники .
- ^ «Цитирование Премии Гёделя 2018» .
- ^ «Цитирование Премии Гёделя 2019 года» .
- ^ «Цитирование Премии Гёделя 2020 года» .
- ^ «Цитирование премии Гёделя 2021 года» .
Рекомендации
- Сайт приза со списком победителей