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

Gödel Prize

В Премия Гёделя ежегодная премия за выдающиеся работы в области теоретическая информатика, предоставленный совместно Европейская ассоциация теоретической информатики (EATCS) и Ассоциация вычислительной техники Специальная группа по алгоритмам и вычислительной теории (ACM SIGACT). Премия названа в честь Курт Гёдель. Связь Гёделя с теоретической информатикой заключается в том, что он первым упомянул "P против NP"вопрос, в письме 1956 г. Джон фон Нейман в котором Гёдель спросил, есть ли НП-полный задача может быть решена за квадратичное или линейное время.[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]
2002Gé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Элиас Кутсупиас, Христос Пападимитриу, Ноам Нисан, Амир Ронен [де], Тим Рафгарден и Эва Тардосдля закладки фундамента алгоритмическая теория игр[3]2009,[документ 28] 2002,[документ 29] 2001[документ 30]
2013Дэн Боне, Мэтью К. Франклин, и Антуан Жудля многопартийных Обмен ключами Диффи-Хеллмана и Схема Боне-Франклина в криптографии[4]2003,[бумага 31]

2004[бумага 32]

2014Рональд Феджин, Амнон Лотем [fr], и Мони Наордля оптимальных алгоритмов агрегирования для промежуточного программного обеспечения[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]

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

  1. ^ Бабай, Ласло; Моран, Шломо (1988), «Игры Артура-Мерлина: рандомизированная система доказательств и иерархия классов сложности» (PDF), Журнал компьютерных и системных наук, 36 (2): 254–276, Дои:10.1016/0022-0000(88)90028-1, ISSN 0022-0000
  2. ^ Goldwasser, S .; Micali, S .; Ракофф, К. (1989), «Сложность знаний интерактивных систем доказательства» (PDF), SIAM Журнал по вычислениям, 18 (1): 186–208, CiteSeerX 10.1.1.397.4002, Дои: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 Журнал по вычислениям, 17 (5): 935–938, CiteSeerX 10.1.1.54.5941, Дои:10.1137/0217058, ISSN 1095-7111
  5. ^ Селепсеньи, Р. (1988), «Метод принудительного перебора для недетерминированных автоматов» (PDF), Acta Informatica, 26 (3): 279–284, Дои:10.1007 / BF00299636, HDL:10338.dmlcz / 120489
  6. ^ Sinclair, A .; Джеррам, М. (1989), "Приближенный счет, равномерное генерирование и быстро перемешивающиеся цепи Маркова", Информация и вычисления, 82 (1): 93–133, Дои:10.1016/0890-5401(89)90067-9, ISSN 0890-5401
  7. ^ Jerrum, M .; Синклер, Алистер (1989), «Приближение к постоянному», SIAM Журнал по вычислениям, 18 (6): 1149–1178, CiteSeerX 10.1.1.431.4190, Дои:10.1137/0218077, ISSN 1095-7111
  8. ^ Халперн, Джозеф; Моисей, Йорам (1990), «Знания и общие знания в распределенной среде» (PDF), Журнал ACM, 37 (3): 549–587, arXiv:cs / 0006009, Дои:10.1145/79147.79161
  9. ^ Тода, Сейноскэ (1991), «PP так же сложен, как иерархия с полиномиальным временем» (PDF), SIAM Журнал по вычислениям, 20 (5): 865–877, CiteSeerX 10.1.1.121.1246, Дои:10.1137/0220053, ISSN 1095-7111
  10. ^ Шор, Питер В. (1997), "Полиномиальные алгоритмы простой факторизации и дискретных логарифмов на квантовом компьютере" (PDF), SIAM Журнал по вычислениям, 26 (5): 1484–1509, arXiv:Quant-ph / 9508027, Дои:10.1137 / S0097539795293172, ISSN 1095-7111[постоянная мертвая ссылка]
  11. ^ Варди, Моше Й .; Вольпер, Пьер (1994), «Рассуждения о бесконечных вычислениях» (PDF), Информация и вычисления, 115 (1): 1–37, Дои:10.1006 / inco.1994.1092, ISSN 0890-5401, заархивировано из оригинал (PDF) на 2011-08-25
  12. ^ Файги, Уриэль; Гольдвассер, Шафи; Ловас, Ласло; Сафра, Шмуэль; Сегеди, Марио (1996), «Интерактивные доказательства и твердость приближающихся клик» (PDF), Журнал ACM, 43 (2): 268–292, Дои:10.1145/226643.226652, ISSN 0004-5411
  13. ^ Арора, Санджив; Сафра, Шмуэль (1998), «Вероятностная проверка доказательств: новая характеристика NP» (PDF), Журнал ACM, 45 (1): 70–122, Дои:10.1145/273865.273901, ISSN 0004-5411, заархивировано из оригинал (PDF) на 2011-06-10
  14. ^ Арора, Санджив; Лунд, Карстен; Мотвани, Раджив; Судан, Мадху; Сегеди, Марио (1998), «Проверка доказательства и трудность задач аппроксимации» (PDF), Журнал ACM, 45 (3): 501–555, CiteSeerX 10.1.1.145.4652, Дои:10.1145/278298.278306, ISSN 0004-5411, заархивировано из оригинал (PDF) на 2011-06-10
  15. ^ Sénizergues, Géraud (2001), "L (A) = L (B) - разрешимость результатов из полных формальных систем", Теор. Comput. Sci., 251 (1): 1–166, Дои:10.1016 / S0304-3975 (00) 00285-1, ISSN 0304-3975
  16. ^ Freund, Y .; Шапире, Р. (1997), «Теоретико-решающее обобщение онлайн-обучения и приложение для повышения квалификации» (PDF), Журнал компьютерных и системных наук, 55 (1): 119–139, Дои:10.1006 / jcss.1997.1504, ISSN 1090-2724
  17. ^ Херлихи, Морис; Шавит, Нир (1999), «Топологическая структура асинхронной вычислимости» (PDF), Журнал ACM, 46 (6): 858–923, CiteSeerX 10.1.1.78.1455, Дои:10.1145/331524.331529. Лекция о премии Гёделя
  18. ^ Сакс, Михаил; Захароглоу, Фотиос (2000), "Без ожидания k-установить согласие невозможно: топология публичных знаний », SIAM Журнал по вычислениям, 29 (5): 1449–1483, Дои:10.1137 / S0097539796307698
  19. ^ Алон, Нога; Матиас, Йосси; Сегеди, Марио (1999), «Пространственная сложность аппроксимации частотных моментов» (PDF), Журнал компьютерных и системных наук, 58 (1): 137–147, Дои:10.1006 / jcss.1997.1545. Впервые представлен на Симпозиум по теории вычислений (STOC) в 1996 году.
  20. ^ Agrawal, M .; Kayal, N .; Саксена, Н. (2004), "ПРИМЕР в П" (PDF), Анналы математики, 160 (2): 781–793, Дои:10.4007 / анналы.2004.160.781, ISSN 0003-486X, заархивировано из оригинал (PDF) на 2011-06-07
  21. ^ Разборов Александр А .; Рудич, Стивен (1997), «Естественные доказательства», Журнал компьютерных и системных наук, 55 (1): 24–35, Дои:10.1006 / jcss.1997.1494, ISSN 0022-0000, ECCC TR94-010
  22. ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2004), «Сглаженный анализ алгоритмов: почему симплексный алгоритм обычно занимает полиномиальное время» (PDF), J. ACM, 51 (3): 385–463, arXiv:математика / 0212413, Дои:10.1145/990308.990310, ISSN 0004-5411[постоянная мертвая ссылка]
  23. ^ Рейнгольд, Омер; Вадхан, Салил; Вигдерсон, Ави (2002), «Энтропийные волны, зигзагообразный граф и новые расширители постоянной степени» (PDF), Анналы математики, 155 (1): 157–187, CiteSeerX 10.1.1.236.8669, Дои:10.2307/3062153, ISSN 0003-486X, JSTOR 3062153, Г-Н 1888797[постоянная мертвая ссылка]
  24. ^ Рейнгольд, Омер (2008), «Ненаправленное подключение в журнальном пространстве», J. ACM, 55 (4): 1–24, Дои:10.1145/1391289.1391291, ISSN 0004-5411[постоянная мертвая ссылка]
  25. ^ Арора, Санджив (1998), "Полиномиальные схемы аппроксимации евклидова коммивояжера и другие геометрические задачи", Журнал ACM, 45 (5): 753–782, CiteSeerX 10.1.1.23.6765, Дои:10.1145/290179.290180, ISSN 0004-5411
  26. ^ Митчелл, Джозеф С. Б. (1999), "Приближенное многоугольное разбиение на гильотине: простая схема аппроксимации за полиномиальное время для геометрической TSP, k-MST и связанных задач", SIAM Журнал по вычислениям, 28 (4): 1298–1309, Дои:10.1137 / S0097539796309764, ISSN 1095-7111
  27. ^ Хостад, Йохан (2001), «Некоторые оптимальные результаты несовместимости» (PDF), Журнал ACM, 48 (4): 798–859, CiteSeerX 10.1.1.638.2808, Дои:10.1145/502090.502098, ISSN 0004-5411
  28. ^ Кутсупиас, Элиас; Пападимитриу, Христос (2009). «Худшее равновесие». Обзор компьютерных наук. 3 (2): 65–69. Дои:10.1016 / j.cosrev.2009.04.003.
  29. ^ Roughgarden, Тим; Тардос, Ева (2002). «Насколько плоха эгоистичная маршрутизация?». Журнал ACM. 49 (2): 236–259. CiteSeerX 10.1.1.147.1081. Дои:10.1145/506147.506153.
  30. ^ Нисан, Ноам; Ронен, Амир (2001). «Дизайн алгоритмических механизмов». Игры и экономическое поведение. 35 (1–2): 166–196. CiteSeerX 10.1.1.21.1731. Дои:10.1006 / игра.1999.0790.
  31. ^ Бонех, Дэн; Франклин, Мэтью (2003). «Шифрование на основе личности из пары Вейля». SIAM Журнал по вычислениям. 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-у. Г-Н 2090557.
  33. ^ Феджин, Рональд; Лотем, Амнон; Наор, Мони (2003). «Оптимальные алгоритмы агрегирования для промежуточного программного обеспечения». Журнал компьютерных и системных наук. 66 (4): 614–656. arXiv:cs / 0204046. Дои:10.1016 / S0022-0000 (03) 00026-6.
  34. ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2011). «Спектральное разрежение графов». SIAM Журнал по вычислениям. 40 (4): 981–1025. arXiv:0808.4134. Дои:10.1137 / 08074489X. ISSN 0097-5397.
  35. ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2013). «Алгоритм локальной кластеризации для массивных графов и его применение к почти линейному разбиению графа по времени». SIAM Журнал по вычислениям. 42 (1): 1–26. arXiv:0809.3232. Дои:10.1137/080744888. ISSN 0097-5397.
  36. ^ Spielman, Daniel A .; Тэн, Шан-Хуа (2014). "Алгоритмы, близкие к линейным по времени для предварительной подготовки и решения симметричных, диагонально доминирующих линейных систем". Журнал SIAM по матричному анализу и приложениям. 35 (3): 835–885. arXiv:cs / 0607105. Дои:10.1137/090771430. ISSN 0895-4798.
  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. Springer-Verlag. С. 265–284. Дои:10.1007/11681878_14. ISBN 978-3-540-32731-8.
  40. ^ Регев, Одед (2009). «На решетках, обучение с ошибками, случайные линейные коды и криптография». Журнал ACM. 56 (6): 1–40. CiteSeerX 10.1.1.215.3543. Дои:10.1145/1568318.1568324.
  41. ^ Динур, Ирит (2007). «Теорема PCP об усилении разрыва». Журнал ACM. 54 (3): 12 – es. Дои:10.1145/1236457.1236459.
  42. ^ «Конструктивное доказательство общей локальной леммы Ловаса». Журнал ACM. 57 (2). 2010. Дои:10.1145/1667053. ISSN 0004-5411.

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

Заметки

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

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