Премия Гёделя
Премия Гёделя — это ежегодная премия за выдающиеся работы в области теоретической информатики , вручаемая совместно Европейской ассоциацией теоретической информатики (EATCS) и Ассоциации вычислительной техники специальной группой по алгоритмам и теории вычислений ( ACM SIGACT ). Премия названа в честь Курта Гёделя . Связь Гёделя с теоретической информатикой заключается в том, что он первым упомянул вопрос « P против NP » в письме 1956 года Джону фон Нейману определенную NP-полную , в котором Гёдель спрашивал , можно ли решить задачу за квадратичное или линейное время . [ 1 ]
Премия Гёделя вручается с 1993 года. Премия вручается поочередно в ICALP (четные годы) и STOC (нечетные годы). STOC — это Симпозиум ACM по теории вычислений , одна из главных североамериканских конференций по теоретической информатике, тогда как ICALP — Международный коллоквиум по автоматам, языкам и программированию , одна из главных европейских конференций в этой области. Чтобы иметь право на получение премии, статья должна быть опубликована в рецензируемом журнале в течение последних 14 (ранее 7) лет. Приз включает в себя вознаграждение в размере 5000 долларов США. [ 2 ]
Лауреат Премии выбирается комитетом из шести человек. Президент EATCS и председатель SIGACT назначают по три члена в комитет на трехлетний срок в шахматном порядке. Комитет поочередно возглавляют представители EATCS и SIGACT.
В отличие от премии Гёделя, которая присуждается за выдающиеся работы, премия Кнута присуждается отдельным лицам за общий вклад в эту область.
Получатели
[ редактировать ]Выигрышные статьи
[ редактировать ]- ^ Бабай, Ласло; Моран, Шломо (1988), «Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности» (PDF) , Journal of Computer and System Sciences , 36 (2): 254–276, doi : 10.1016/0022 -0000(88)90028-1 , ISSN 0022-0000
- ^ Гольдвассер, С.; Микали, С.; Ракофф, К. (1989), «Сложность знаний интерактивных систем доказательства» (PDF) , SIAM Journal on Computing , 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 февраля 2012 г.
- ^ Иммерман, Нил (1988), «Недетерминированное пространство закрыто при дополнении» (PDF) , SIAM Journal on Computing , 17 (5): 935–938, CiteSeerX 10.1.1.54.5941 , doi : 10.1137/0217058 , ISSN 1095-7111
- ^ Селепсени, Р. (1988), «Метод принудительного перебора недетерминированных автоматов» (PDF) , Acta Informatica , 26 (3): 279–284, doi : 10.1007/BF00299636 , hdl : 10338.dmlcz/120489 , S2CID 10838178
- ^ Синклер, А.; Джеррум, М. (1989), «Приблизительный подсчет, равномерное генерирование и быстрое перемешивание цепей Маркова», Information and Computation , 82 (1): 93–133, doi : 10.1016/0890-5401(89)90067-9 , ISSN 0890 -5401
- ^ Джеррум, М.; Синклер, Алистер (1989), «Приближение к постоянному», SIAM Journal on Computing , 18 (6): 1149–1178, CiteSeerX 10.1.1.431.4190 , doi : 10.1137/0218077 , ISSN 1095-7111
- ^ Халперн, Джозеф ; Моисей, Йорам (1990), «Знания и общие знания в распределенной среде» (PDF) , Journal of the ACM , 37 (3): 549–587, arXiv : cs/0006009 , doi : 10.1145/79147.79161 , S2CID 52151232
- ^ Тода, Сейносуке (1991), «ПП так же сложна, как иерархия с полиномиальным временем» (PDF) , SIAM Journal on Computing , 20 (5): 865–877, CiteSeerX 10.1.1.121.1246 , doi : 10.1137/0220053 , ISSN 1095-7111 , заархивировано из оригинала (PDF) 3 марта 2016 г. , получено 8 июня 2010 г.
- ^ Шор, Питер В. (1997), «Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере», SIAM Journal on Computing , 26 (5): 1484–1509, arXiv : quant-ph/9508027 , doi : 10.1137/S0097539795293172 , ISSN 1095-7111 , S2CID 2337707
- ^ Варди, Моше Ю.; Вулпер, Пьер (1994), «Рассуждения о бесконечных вычислениях» (PDF) , Information and Computation , 115 (1): 1–37, doi : 10.1006/inco.1994.1092 , ISSN 0890-5401 , заархивировано из оригинала (PDF) 25 августа 2011 г.
- ^ Файги, Уриэль; Гольдвассер, Шафи; Ловас, Ласло; Сафра, Шмуэль; Сегеди, Марио (1996), «Интерактивные доказательства и жесткость аппроксимирующих клик» (PDF) , Журнал ACM , 43 (2): 268–292, doi : 10.1145/226643.226652 , ISSN 0004-5411
- ^ Арора, Санджив; Сафра, Шмуэль (1998), «Вероятностная проверка доказательств: новая характеристика NP» (PDF) , Журнал ACM , 45 (1): 70–122, doi : 10.1145/273865.273901 , ISSN 0004-5411 , S2CID 751563 , заархивировано из оригинала (PDF) 10 июня 2011 г.
- ^ Арора, Санджив; Лунд, Карстен; Мотвани, Раджив; Судан, Мадху; Сегеди, Марио (1998), «Проверка доказательств и сложность задач аппроксимации» (PDF) , Journal of the ACM , 45 (3): 501–555, CiteSeerX 10.1.1.145.4652 , doi : 10.1145/278298.278306 , ISSN 0004 -5411 , S2CID 8561542 , заархивировано из оригинала (PDF) 10 июня 2011 г.
- ^ Сенизерг, Жеро (2001), «L (A) = L (B)? Разрешимость следует из полных формальных систем», Теория. Вычислить. наук. , 251 (1): 1–166, doi : 10.1016/S0304-3975(00)00285-1 , ISSN 0304-3975
- ^ Фройнд, Ю.; Шапире, Р.Э. (1997), «Теоретико-решательное обобщение онлайн-обучения и применение к повышению» (PDF) , Journal of Computer and System Sciences , 55 (1): 119–139, doi : 10.1006/jcss. 1997.1504 , ISSN 1090-2724.
- ^ Херлихи, Морис ; Шавит, Нир (1999), «Топологическая структура асинхронной вычислимости» (PDF) , Journal of the 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 году.
- ^ Агравал, М.; Каял, Н.; Саксена, Н. (2004), «ПРАЙМЫ находятся в P», Annals of Mathematics , 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
- ^ Спилман, Дэниел А.; Тенг, Шан-Хуа (2004), «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время», J. ACM , 51 (3): 385–463, arXiv : math/0212413 , doi : 10.1145/990308.990310 , ISSN 0004-5411
- ^ Рейнгольд, Омер; Вадхан, Салил; Вигдерсон, Ави (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
- ^ Рейнгольд, Омер (2008), «Ненаправленная связность в пространстве журналов» , J. ACM , 55 (4): 1–24, doi : 10.1145/1391289.1391291 , ISSN 0004-5411 , S2CID 207168478 [ постоянная мертвая ссылка ]
- ^ Арора, Санджив (1998), «Схемы аппроксимации полиномиального времени для евклидова коммивояжера и других геометрических задач», Journal of the 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
- ^ Хостад, Йохан (2001), «Некоторые оптимальные результаты неаппроксимируемости» (PDF) , Journal of the 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. дои : 10.1016/j.cosrev.2009.04.003 .
- ^ Рафгарден, Тим; Тардос, Ева (2002). «Насколько плоха эгоистичная маршрутизация?». Журнал АКМ . 49 (2): 236–259. CiteSeerX 10.1.1.147.1081 . дои : 10.1145/506147.506153 . S2CID 207638789 .
- ^ Нисан, Ноам; Ронен, Амир (2001). «Проектирование алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. CiteSeerX 10.1.1.21.1731 . дои : 10.1006/game.1999.0790 .
- ^ Боне, Дэн; Франклин, Мэтью (2003). «Шифрование на основе личности из пары Вейля». SIAM Journal по вычислительной технике . 32 (3): 586–615. CiteSeerX 10.1.1.66.1131 . дои : 10.1137/S0097539701398521 . МР 2001745 .
- ^ Жу, Антуан (2004). «Протокол одного раунда для трехстороннего протокола Диффи-Хеллмана» . Журнал криптологии . 17 (4): 263–276. дои : 10.1007/s00145-004-0312-y . МР 2090557 . S2CID 3350730 .
- ^ Феджин, Рональд; Лотем, Амнон; Наор, Мони (2003). «Оптимальные алгоритмы агрегации для промежуточного программного обеспечения». Журнал компьютерных и системных наук . 66 (4): 614–656. arXiv : cs/0204046 . дои : 10.1016/S0022-0000(03)00026-6 .
- ^ Спилман, Дэниел А.; Тенг, Шан-Хуа (2011). «Спектральная разреженность графов». SIAM Journal по вычислительной технике . 40 (4): 981–1025. arXiv : 0808.4134 . дои : 10.1137/08074489X . ISSN 0097-5397 . S2CID 9646279 .
- ^ Спилман, Дэниел А.; Тенг, Шан-Хуа (2013). «Алгоритм локальной кластеризации для массивных графов и его применение к почти линейному разбиению временных графов». SIAM Journal по вычислительной технике . 42 (1): 1–26. arXiv : 0809.3232 . дои : 10.1137/080744888 . ISSN 0097-5397 . S2CID 9151077 .
- ^ Спилман, Дэниел А.; Тенг, Шан-Хуа (2014). «Алгоритмы почти линейного времени для предварительной обработки и решения симметричных линейных систем с диагональным преобладанием». Журнал SIAM по матричному анализу и приложениям . 35 (3): 835–885. arXiv : cs/0607105 . дои : 10.1137/090771430 . ISSN 0895-4798 . S2CID 1750944 .
- ^ Брукс, Стивен (2007). «Семантика логики параллельного разделения» (PDF) . Теоретическая информатика . 375 (1–3): 227–270. дои : 10.1016/j.tcs.2006.12.034 .
- ^ О'Хирн, Питер (2007). «Ресурсы, параллелизм и локальное мышление» (PDF) . Теоретическая информатика . 375 (1–3): 271–307. дои : 10.1016/j.tcs.2006.12.035 .
- ^ Дворк, Синтия; МакШерри, Фрэнк; Ниссим, Кобби; Смит, Адам (2006). Халеви, Шай; Рабин, Таль (ред.). Калибровка шума по чувствительности при анализе частных данных . Теория криптографии (ТКС). Конспекты лекций по информатике. Том. 3876. Шпрингер-Верлаг. стр. 265–284. дои : 10.1007/11681878_14 . ISBN 978-3-540-32731-8 .
- ^ Регев, Одед (2009). «О решетках, обучении с ошибками, случайных линейных кодах и криптографии». Журнал АКМ . 56 (6): 1–40. CiteSeerX 10.1.1.215.3543 . дои : 10.1145/1568318.1568324 . S2CID 207156623 .
- ^ Динур, Ирит (2007). «Теорема PCP об усилении щели» . Журнал АКМ . 54 (3): 12–с. дои : 10.1145/1236457.1236459 . S2CID 53244523 .
- ^ «Конструктивное доказательство общей локальной леммы Ловаса». Журнал АКМ . 57 (2). 2010. дои : 10.1145/1667053 . ISSN 0004-5411 .
- ^ Булатов, Андрей А. (2013). «Сложность проблемы удовлетворения ограничений счета». Журнал АКМ . 60 (5). Ассоциация вычислительной техники: 1–41. дои : 10.1145/2528400 . ISSN 0004-5411 . S2CID 8964233 .
- ^ Дайер, Мартин; Ричерби, Дэвид (2013). «Эффективная дихотомия для проблемы удовлетворения ограничений подсчета». SIAM Journal по вычислительной технике . 42 (3). Общество промышленной и прикладной математики (SIAM): 1245–1274. arXiv : 1003.3879 . дои : 10.1137/100811258 . ISSN 0097-5397 . S2CID 1247279 .
- ^ Цай, Джин-И; Чэнь, Си (22 июня 2017 г.). «Сложность подсчета CSP с комплексными весами». Журнал АКМ . 64 (3). Ассоциация вычислительной техники: 1–39. arXiv : 1111.2384 . дои : 10.1145/2822891 . ISSN 0004-5411 . S2CID 1053684 .
- ^ Бракерски, Цвика; Вайкунтанатан, Винод (январь 2014 г.). «Эффективное полностью гомоморфное шифрование из (стандартного) $\mathsf{LWE}$» . SIAM Journal по вычислительной технике . 43 (2): 831–871. дои : 10.1137/120868669 . hdl : 1721.1/115488 . ISSN 0097-5397 . S2CID 8831240 .
- ^ Бракерски, Цвика; Джентри, Крейг; Вайкунтанатан, Винод (2012). «(Уровневое) полностью гомоморфное шифрование без начальной загрузки» . Материалы 3-й конференции «Инновации в теоретической информатике» . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 309–325. дои : 10.1145/2090236.2090262 . ISBN 9781450311151 . S2CID 2602543 .
- ^ Фиорини, Самуэль; Массар, Серж; Покутта, Себастьян; Тивари, Ханс Радж; де Вольф, Рональд (2015). «Экспоненциальные нижние границы для многогранников в комбинаторной оптимизации» . Журнал АКМ . 62 (2): 17:1–17:23. arXiv : 1111.0837 . дои : 10.1145/2716307 . S2CID 7372000 .
- ^ Ротвосс, Томас (2017). «Соответствующий многогранник имеет экспоненциальную сложность расширения» . Журнал АКМ . 64 (6): 41:1–41:19. arXiv : 1311.2369 . дои : 10.1145/3127497 . S2CID 47045361 .
- ^ Уильямс, Райан (июнь 2011 г.). «Нижние границы неравномерной цепи ACC» . 2011 26-я ежегодная конференция IEEE по сложности вычислений . IEEE. стр. 115–125. дои : 10.1109/ccc.2011.36 . ISBN 978-1-4577-0179-5 .
См. также
[ редактировать ]Примечания
[ редактировать ]- ^ «Письмо Гёделя» . 12 февраля 2009 г.
- ^ Jump up to: а б «Премия Гёделя 2017» . Европейская ассоциация теоретической информатики . ЕАТКС . Проверено 29 марта 2017 г.
- ^ «Три статьи, цитируемые как закладывающие основу роста в алгоритмической теории игр» . 16 мая 2012 года. Архивировано из оригинала 18 июля 2013 года . Проверено 16 мая 2012 г.
- ^ ACM Group вручает премию Гёделя за достижения в криптографии: трое ученых-компьютерщиков отмечены за инновации, повышающие безопасность. Архивировано 1 июня 2013 г. в Wayback Machine , Ассоциация вычислительной техники , 29 мая 2013 г.
- ^ Получатели достигли революционных результатов в агрегировании данных из нескольких источников , Ассоциация вычислительной техники , 30 апреля 2014 г.
- ^ Объявление о премии Гёделя 2015. Архивировано 9 декабря 2017 г. в Wayback Machine Ассоциацией вычислительной техники .
- ^ «Цитата на премию Гёделя 2018» .
- ^ «Цитата на премию Гёделя 2019» .
- ^ «Цитата на премию Гёделя 2020» .
- ^ «Цитата на премию Гёделя 2021» .
- ^ «Цитата на премию Гёделя 2022» .
- ^ «Цитата на премию Гёделя 2023» .
- ^ «Цитата на премию Гёделя 2024» .