Премія Геделя () — щорічна премія за визначні праці у теоретичній інформатиці, яку присуджують з 1993 року організації ACM та EATCS (). Її названо на честь австрійського логіка і математика Курта Геделя (1906—1978).
Премія включає у себе нагороду у розмірі 5000 доларів США. Премію вручають або на американському симпозіумі STOC (), або на європейській конференції ICALP (). До участі приймають усі роботи, час від першої публікації яких не перевищує 14 років.
Лауреати
Рік Імена За що Рік публікації1993 Ласло Бабай, Шафі Ґолдвассер, Сільвіо Мікалі, Шломо Моран та Чарльз Рекоф за розробку інтерактивних систем доведення 1988, 19891994 Йохан Хостад за експоненційну нижню межу розміру логічних циклів з константною глибиною (для функції парності). 19891995 Ніл Іммерман та Роберт Селепчені за теорему Іммермана-Селепчені стосовно недетермінованої просторової складності 1988, 19881996 Марк Джерум та Елістер Сінклер за роботу над ланцюгами Маркова і апроксимацією перманента 1989, 19891997 Джозеф Галперн та Йорам Мосес за визначення формального запису «знань» у розподілених середовищах 19901998 Сеіносуке Тода за теорему Тода, яка показала зв'язок між обчисленими розв'язками (PP) і чергуванням кванторів (PH) 19911999 Пітер Шор за алгоритм Шора для факторизації чисел за поліноміальний час на квантовому комп'ютері 19972000 Моше Варді та П'єр Волпер за роботу над перевіркою моделей із скінченними автоматами 19942001 Сенджев Арора, Уріель Фейґе, Шафі Ґолдвассер, Ларстен Лунд, Ласло Ловас, Раджів Мотвані, Шмуель Сафра, Мадху Судан та Маріо Сеґеді за PCP-теорему та її застосування до складності апроксимації 1996, 1998, 19982002 Жеро Сенізерґ за доведення того, що еквівалентність детермінованих стекових автоматів є розв'язуваною 20012003 Йоув Фруенд та Роберт Шапіро за алгоритм AdaBoost 19972004 Моріс Герлігу, Майкл Сакс, Нір Шавіт та Фотіос Загароґлоу за застосування топології до теорії розподілених обчислень 1999. Gödel prize lecture, 20002005 Ноґа Алон, Йоссі Матіас та Mario Szegedy за їхній фундаментальний внесок до потокових алгоритмів 1999. First presented at the Symposium on Theory of Computing (STOC) in 1996.2006 Маніндра Аґравал, Нірадж Каяль, Нітін Саксена за тест простоти AKS 20042007 Олександр Разборов, Стівен Редік за природні доведення 19972008 Шанг-Хуа Тенг, Деніель Спілмен за згладжений аналіз алгоритмів 20042009 Омер Реінгольд, Саліл Вадген, Аві Віґдерсон за зигзаговий добуток графів та ненапрямлену зв'язність у логарифмічному просторі 2002, 20082010 Сенджев Арора, Джозеф Мітчел за їхнє одночасне відкриття поліноміальної апроксимаційної схеми для евклідової задачі комівояжера (ETSP) 1998, 19992011 Йохан Хастад за покращення PCP-теореми за допомогою нових імовірнісних верифікаторів, що дозволяють перевірити належність слова до NP-мови, прочитавши не більше ніж три біти з відповідного доведення 20012012 , Христос Пападімітріу, Noam Nisan, , Tim Roughgarden і Ева Тардош за закладення основ 2009, 2002, 20012013 Ден Бонех, Matthew K. Franklin, and Antoine Joux за багатосторонній протокол Діффі-Геллмана та в криптографіїACM Group Presents Gödel Prize for Advances in Cryptography: Three Computer Scientists Cited for Innovations that Improve Security , Association for Computing Machinery, May 29, 2013. 2003, 20042014 Ronald Fagin, , and Moni Naor за оптимальні алгоритми агрегації для проміжного програмного забезпечення Recipients Achieved Groundbreaking Results for Aggregating Data from Multiple Sources, Association for Computing Machinery, April 30, 2014. 2003,2015 Деніел Спілмен, Shanghua Teng за низку робіт з практично-лінійних розв'язувачів Лапласа2015 Gödel Prize announcement by Association for Computing Machinery. 2011 2013 20142016Stephen Brookes and Peter W. O'Hearnза винахід 2007, 20072017Cynthia Dwork, , Kobbi Nissim, та за дослідження диференційної приватності20062018 Oded Regevза введення у розгляд задачи 20092019 Іріт Дінурза нове доведення PCP-теореми2007
Переможні праці
Примітки
Посилання Офіційний сайт зі списком лауреатів