stringtranslate.com

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

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

Премия Гёделя вручается с 1993 года. Премия вручается поочередно в ICALP (четные годы) и STOC (нечетные годы). STOC — это Симпозиум ACM по теории вычислений , одна из главных североамериканских конференций по теоретической информатике, тогда как ICALP — Международный коллоквиум по автоматам, языкам и программированию , одна из главных европейских конференций в этой области. Чтобы иметь право на получение премии, статья должна быть опубликована в рецензируемом журнале в течение последних 14 (ранее 7) лет. Приз включает в себя вознаграждение в размере 5000 долларов США. [2]

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

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

Получатели

Выигрышные статьи

  1. ^ Бабай, Ласло; Моран, Шломо (1988), «Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности» (PDF) , Journal of Computer and System Sciences , 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) 22 февраля 2012 г.
  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), «Приблизительный подсчет, равномерное генерирование и быстрое смешивание цепей Маркова», Information and Computation , 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) , Journal of the ACM , 37 (3): 549–587, arXiv : cs/0006009 , doi : 10.1145/79147.79161, S2CID  52151232
  9. ^ Тода, Сейносуке (1991), «PP так же сложен, как иерархия с полиномиальным временем» (PDF) , SIAM Journal on Computing , 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) , Information and Computation , 115 (1): 1–37, doi : 10.1006/inco.1994.1092, ISSN  0890-5401, заархивировано из оригинала (PDF) 25 августа 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) 10 июня 2011 г.
  14. ^ Арора, Санджив; Лунд, Карстен; Мотвани, Раджив; Судан, Мадху; Сегеди, Марио (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 г. 
  15. ^ Сенизерг, Жеро (2001), «L (A) = L (B)? Разрешимость является результатом полных формальных систем», Theor. Вычислить. наук. , 251 (1): 1–166, doi : 10.1016/S0304-3975(00)00285-1, ISSN  0304-3975
  16. ^ Фрейнд, Ю.; Шапире, 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) , Journal of the 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) , Journal of Computer and System Sciences , 58 (1): 137–147, doi : 10.1006/jcss.1997.1545. Впервые представлено на Симпозиуме по теории вычислений (STOC) в 1996 году.
  20. ^ Агравал, М.; Каял, Н.; Саксена, Н. (2004), «ПРАЙМЫ находятся в 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), «Схемы аппроксимации полиномиального времени для евклидова коммивояжера и других геометрических задач», Journal of the 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. ^ Хостад, Йохан (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). «Насколько плоха эгоистичная маршрутизация?». Журнал АКМ . 49 (2): 236–259. CiteSeerX 10.1.1.147.1081 . дои : 10.1145/506147.506153. S2CID  207638789. 
  30. ^ Нисан, Ноам; Ронен, Амир (2001). «Проектирование алгоритмических механизмов». Игры и экономическое поведение . 35 (1–2): 166–196. CiteSeerX 10.1.1.21.1731 . дои : 10.1006/game.1999.0790. 
  31. ^ Боне, Дэн; Франклин, Мэтью (2003). «Шифрование на основе личности из пары Вейля». SIAM Journal по вычислительной технике . 32 (3): 586–615. CiteSeerX 10.1.1.66.1131 . дои : 10.1137/S0097539701398521. МР  2001745. 
  32. ^ Жу, Антуан (2004). «Протокол одного раунда для трехстороннего Диффи-Хеллмана». Журнал криптологии . 17 (4): 263–276. дои : 10.1007/s00145-004-0312-y . MR  2090557. S2CID  3350730.
  33. ^ Феджин, Рональд; Лотем, Амнон; Наор, Мони (2003). «Оптимальные алгоритмы агрегации для промежуточного программного обеспечения». Журнал компьютерных и системных наук . 66 (4): 614–656. arXiv : cs/0204046 . дои : 10.1016/S0022-0000(03)00026-6.
  34. ^ Спилман, Дэниел А.; Тенг, Шан-Хуа (2011). «Спектральная разреженность графов». SIAM Journal по вычислительной технике . 40 (4): 981–1025. arXiv : 0808.4134 . дои : 10.1137/08074489X. ISSN  0097-5397. S2CID  9646279.
  35. ^ Спилман, Дэниел А.; Тенг, Шан-Хуа (2013). «Алгоритм локальной кластеризации для массивных графов и его применение к почти линейному разбиению временных графов». SIAM Journal по вычислительной технике . 42 (1): 1–26. arXiv : 0809.3232 . дои : 10.1137/080744888. ISSN  0097-5397. S2CID  9151077.
  36. ^ Спилман, Дэниел А.; Тенг, Шан-Хуа (2014). «Алгоритмы почти линейного времени для предварительной обработки и решения симметричных линейных систем с диагональным преобладанием». Журнал SIAM по матричному анализу и приложениям . 35 (3): 835–885. arXiv : cs/0607105 . дои : 10.1137/090771430. ISSN  0895-4798. S2CID  1750944.
  37. ^ Брукс, Стивен (2007). «Семантика логики параллельного разделения» (PDF) . Теоретическая информатика . 375 (1–3): 227–270. дои : 10.1016/j.tcs.2006.12.034.
  38. ^ О'Хирн, Питер (2007). «Ресурсы, параллелизм и локальное мышление» (PDF) . Теоретическая информатика . 375 (1–3): 271–307. дои : 10.1016/j.tcs.2006.12.035 .
  39. ^ Дворк, Синтия; МакШерри, Фрэнк; Ниссим, Кобби; Смит, Адам (2006). Халеви, Шай; Рабин, Таль (ред.). Калибровка шума по чувствительности при анализе частных данных . Теория криптографии (ТКС). Конспекты лекций по информатике. Том. 3876. Шпрингер-Верлаг. стр. 265–284. дои : 10.1007/11681878_14 . ISBN 978-3-540-32731-8.
  40. ^ Регев, Одед (2009). «О решетках, обучении с ошибками, случайных линейных кодах и криптографии». Журнал АКМ . 56 (6): 1–40. CiteSeerX 10.1.1.215.3543 . дои : 10.1145/1568318.1568324. S2CID  207156623. 
  41. ^ Динур, Ирит (2007). «Теорема PCP об усилении разрыва». Журнал АКМ . 54 (3): 12–с. дои : 10.1145/1236457.1236459. S2CID  53244523.
  42. ^ «Конструктивное доказательство общей локальной леммы Ловаса». Журнал АКМ . 57 (2). 2010. дои : 10.1145/1667053. ISSN  0004-5411.
  43. ^ Булатов, Андрей А. (2013). «Сложность проблемы удовлетворения ограничений счета». Журнал АКМ . 60 (5). Ассоциация вычислительной техники (ACM): 1–41. дои : 10.1145/2528400. ISSN  0004-5411. S2CID  8964233.
  44. ^ Дайер, Мартин; Ричерби, Дэвид (2013). «Эффективная дихотомия для проблемы удовлетворения ограничений подсчета». SIAM Journal по вычислительной технике . 42 (3). Общество промышленной и прикладной математики (SIAM): 1245–1274. arXiv : 1003.3879 . дои : 10.1137/100811258. ISSN  0097-5397. S2CID  1247279.
  45. ^ Цай, Джин-И; Чэнь, Си (22 июня 2017 г.). «Сложность подсчета CSP с комплексными весами». Журнал АКМ . 64 (3). Ассоциация вычислительной техники (ACM): 1–39. arXiv : 1111.2384 . дои : 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. ^ Бракерски, Звика; Джентри, Крейг; Вайкунтанатан, Винод (2012). «(Уровневое) полностью гомоморфное шифрование без начальной загрузки». Материалы 3-й конференции «Инновации в теоретической информатике» . Нью-Йорк, Нью-Йорк, США: ACM Press. стр. 309–325. дои : 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). «Соответствующий многогранник имеет экспоненциальную сложность расширения». Журнал АКМ . 64 (6): 41:1–41:19. arXiv : 1311.2369 . дои : 10.1145/3127497. S2CID  47045361.

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

Примечания

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

Рекомендации