Премия Гёделя - Gödel Prize
Премия Гёделя - это ежегодная премия за выдающиеся работы в области теоретической информатики , присуждаемая совместно Европейской ассоциацией теоретической информатики (EATCS) и Специальной группой по алгоритмам и вычислительной теории Ассоциации вычислительной техники ( ACM SIGACT ). Премия названа в честь Курта Гёделя . Связь Гёделя с теоретической информатикой заключается в том, что он первым упомянул вопрос « P против NP » в письме 1956 года Джону фон Нейману, в котором Гёдель спросил, может ли определенная NP-полная задача быть решена за квадратичное или линейное время.
Премия Гёделя вручается с 1993 года. Премия присуждается либо на STOC ( Симпозиум ACM по теории вычислений , одна из основных североамериканских конференций по теоретической информатике), либо на ICALP ( Международный коллоквиум по автоматам, языкам и программированию , один из основные европейские конференции в этой области). Чтобы иметь право на получение приза, статья должна быть опубликована в рецензируемом журнале в течение последних 14 (ранее 7) лет. Приз включает вознаграждение в размере 5000 долларов США.
Победителя Премии выбирает комиссия из шести человек. Президент EATCS и председатель SIGACT назначают по три члена комитета на трехлетний срок в шахматном порядке. Комитет возглавляют поочередно представители EATCS и SIGACT.
Получатели
Год | Имя (а) | Примечания | Год публикации | |
---|---|---|---|---|
1993 г. | Ласло Бабай , Шафи Гольдвассер , Сильвио Микали , Шломо Моран и Чарльз Ракофф | для разработки интерактивных систем доказательства | 1988, 1989 | |
1994 г. | Йохан Хастад | Для экспоненциального нижней границы по размеру постоянной глубины булевых схем (для функции четности ). | 1989 г. | |
1995 г. | Нил Иммерман и Роберт Селепсеньи | для теоремы Иммермана – Селепсеньи о недетерминированной пространственной сложности | 1988, 1988 | |
1996 г. | Марк Джеррам и Алистер Синклер | за работу над цепями Маркова и приближением перманента матрицы | 1989, 1989 | |
1997 г. | Джозеф Халперн и Йорам Мозес | для определения формального понятия «знания» в распределенных средах | 1990 г. | |
1998 г. | Сейноске Тода | для теоремы Тоды, которая показала связь между подсчетом решений ( PP ) и чередованием кванторов ( PH ) | 1991 г. | |
1999 г. | Петр Шор | для алгоритма Шора для факторинговых чисел в полиномиальное время на квантовом компьютере | 1997 г. | |
2000 г. | Моше Ю. Варди и Пьер Вольпер | для работы по темпоральной логике с конечными автоматами | 1994 г. | |
2001 г. | Санджив Арора , Уриэль Фейге , Шафи Гольдвассер , Карстен Лунд , Ласло Ловас , Раджив Мотвани , Шмуэль Сафра , Мадху Судан и Марио Сегеди | для теоремы PCP и ее приложений к трудности аппроксимации | 1996, 1998, 1998 | |
2002 г. | Géraud Sénizergues | для доказательства того, что эквивалентность детерминированных магазинных автоматов является разрешимой | 2001 г. | |
2003 г. | Йоав Фройнд и Роберт Шапир | для алгоритма AdaBoost в машинном обучении | 1997 г. | |
2004 г. | Морис Херлихи , Майкл Сакс , Нир Шавит и Фотиос Захароглу | для приложений топологии к теории распределенных вычислений | 1999, 2000 | |
2005 г. | Нога Алон , Йоси Матиас и Марио Сегеди | за их фундаментальный вклад в алгоритмы потоковой передачи | 1999 г. | |
2006 г. | Маниндра Агравал , Нирадж Каял , Нитин Саксена | для теста простоты AKS | 2004 г. | |
2007 г. | Александр Разборов , Стивен Рудич | для естественных доказательств | 1997 г. | |
2008 г. | Даниэль Спилман , Шанхуа Тэн | для сглаженного анализа алгоритмов | 2004 г. | |
2009 г. | Омер Рейнгольд , Салил Вадхан , Ави Вигдерсон | для зиг-заг продукт из графиков и неориентированного соединений в лог пространстве | 2002, 2008 | |
2010 г. | Санджив Арора , Джозеф С.Б. Митчелл | за их одновременное открытие схемы полиномиального приближения (PTAS) для евклидовой задачи коммивояжера (ETSP) | 1998,
1999 г. |
|
2011 г. | Йохан Хастад | для доказательства оптимальных результатов о приближаемости различных комбинаторных задач | 2001 г. | |
2012 г. | Элиас Koutsoupias , Пападимитий , Ноам Нисан , Амир Ронен , Тим Роугарден и Эва Тардос | для создания основ алгоритмической теории игр | 2009, 2002, 2001 | |
2013 | Дэн Боне , Мэтью К. Франклин и Антуан Жу | для многостороннего обмена ключами Диффи-Хеллмана и схемы Боне-Франклина в криптографии | 2003 г.,
2004 г. |
|
2014 г. | Рональд Феджин , Амнон Лотем и Мони Наор | для оптимальных алгоритмов агрегирования для промежуточного программного обеспечения | 2003 г., | |
2015 г. | Даниэль Спилман , Шанхуа Тэн | за серию статей о лапласовских решателях с почти линейным временем |
2011 2013 2014 |
|
2016 г. | Стивен Брукс и Питер У. О'Хирн | за изобретение параллельной логики разделения | 2007, 2007 | |
2017 г. | Синтия Дворк , Фрэнк МакШерри , Кобби Ниссим и Адам Д. Смит | за изобретение дифференциальной конфиденциальности | 2006 г. | |
2018 г. | Одед Регев | за введение в проблему обучения с ошибками | 2009 г. | |
2019 г. | Ирит Динур | за новое доказательство теоремы PCP путем усиления разрыва | 2007 г. | |
2020 г. | Робин Мозер и Габор Тардос | для их конструктивного доказательства в локальной леммы Lovász | 2010 г. | |
2021 г. | Андрей Булатов, Цзинь-И Цай, Си Чен, Мартин Дайер и Дэвид Ричерби | за их работу по классификации подсчета сложности из проблем удовлетворения ограничений | 2013
2013 2017 |