Loading AI tools
нагорода за видатні роботи в галузі теоретичної інформатики З Вікіпедії, вільної енциклопедії
Премія Геделя (англ. Gödel Prize) — щорічна премія за визначні праці у теоретичній інформатиці, яку присуджують з 1993 року організації ACM та EATCS (англ. European Association for Theoretical Computer Science). Її названо на честь австрійського логіка і математика Курта Геделя (1906—1978).
Премія Геделя англ. Gödel Prize | ||||
Країна | США | |||
---|---|---|---|---|
Тип | наукова нагородаd і інформаційний списокd | |||
На честь: | Курт Гедель | |||
Нагородження | ||||
Засновано: | 1992 | |||
Нагороджені: | ||||
Категорія:Лауреати премії Геделя (13) | ||||
Черговість | ||||
Премія Геделя у Вікісховищі |
Премія включає у себе нагороду у розмірі 5000 доларів США. Премію вручають або на американському симпозіумі STOC (англ. Symposium on Theory of Computing), або на європейській конференції ICALP (англ. International Colloquium on Automata, Languages and Programming). До участі приймають усі роботи, час від першої публікації яких не перевищує 14 років.
Рік | Імена | За що | Рік публікації |
---|---|---|---|
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] |
2002 | Жеро Сенізерґ | за доведення того, що еквівалентність детермінованих стекових автоматів є розв'язуваною | 2001[праця 15] |
2003 | Йоув Фруенд та Роберт Шапіро | за алгоритм AdaBoost | 1997[праця 16] |
2004 | Моріс Герлігу, Майкл Сакс, Нір Шавіт та Фотіос Загароґлоу | за застосування топології до теорії розподілених обчислень | 1999[праця 17], 2000[праця 18] |
2005 | Ноґа Алон, Йоссі Матіас та Mario Szegedy | за їхній фундаментальний внесок до потокових алгоритмів | 1999[праця 19] |
2006 | Маніндра Аґравал, Нірадж Каяль, Нітін Саксена | за тест простоти AKS | 2004[праця 20] |
2007 | Олександр Разборов, Стівен Редік | за природні доведення | 1997[праця 21] |
2008 | Шанг-Хуа Тенг, Деніель Спілмен | за згладжений аналіз алгоритмів | 2004[праця 22] |
2009 | Омер Реінгольд, Саліл Вадген, Аві Віґдерсон | за зигзаговий добуток графів та ненапрямлену зв'язність у логарифмічному просторі | 2002[праця 23], 2008[праця 24] |
2010 | Сенджев Арора, Джозеф Мітчел | за їхнє одночасне відкриття поліноміальної апроксимаційної схеми для евклідової задачі комівояжера (ETSP) | 1998[праця 25],
1999[праця 26] |
2011 | Йохан Хастад | за покращення PCP-теореми за допомогою нових імовірнісних верифікаторів, що дозволяють перевірити належність слова до NP-мови, прочитавши не більше ніж три біти з відповідного доведення | 2001[праця 27] |
2012 | Elias Koutsoupias[de], Христос Пападімітріу, Noam Nisan, Amir Ronen[de], Tim Roughgarden і Ева Тардош | за закладення основ алгоритмічної теорії ігор[en][1] | 2009,[праця 28] 2002,[праця 29] 2001[праця 30] |
2013 | Ден Бонех, Matthew K. Franklin, and Antoine Joux | за багатосторонній протокол Діффі-Геллмана та схему Боєна-Франкліна[en] в криптографії[2] | 2003,[праця 31]
2004[праця 32] |
2014 | Ronald Fagin, Amnon Lotem[fr], and Moni Naor | за оптимальні алгоритми агрегації для проміжного програмного забезпечення[3] | 2003,[праця 33] |
2015 | Деніел Спілмен, Shanghua Teng | за низку робіт з практично-лінійних розв'язувачів Лапласа[4] |
2011[праця 34] 2013[праця 35] 2014[праця 36] |
2016 | Stephen Brookes and Peter W. O'Hearn | за винахід Паралельної логіки розділення[en] | 2007[праця 37], 2007[праця 38] |
2017[5] | Cynthia Dwork, Frank McSherry[fr], Kobbi Nissim, та Adam D. Smith[fr] | за дослідження диференційної приватності | 2006[праця 39] |
2018[6] | Oded Regev | за введення у розгляд задачи навчання з помилками[en] | 2009[праця 40] |
2019[7] | Іріт Дінур | за нове доведення PCP-теореми | 2007[праця 41] |
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.