Премія Геделя

Премія Геделя ( англ. Gdel Prize ) - Премія в галузі теорії обчислювальних систем імені Курта Геделя, що вручається щорічно організаціями ACM SIGACT (Special Interest Group on Algorithms and Computation Theory) та EATCS (European Association for Theoretical Computer Science) за видатні праці з логіці і теоретичної інформатики.

Премія вручається з 1993 і супроводжується грошовою винагородою розміром в 5000 доларів США. Нагородження проходить або на американському симпозіумі STOC (Symposium on Theory of Computing), або на європейській конференції ICALP (International Colloquium on Automata, Languages ​​and Programming). [1] Основною вимогою до роботи є дата першої публікації - до номінації допускаються лише труди не старше 14 років.


1. Лауреати

Рік Ім'я Примітки
1993 Ласло Бабаї, Шафі Гольдвассер, Сільвіо Міка, Шломо Моран і Чарльз Ракофф (Lszl Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, Charles Rackoff) за розробку інтерактивних систем доказів
1994 Йохан Хостад (Johan Hstad) за доказ приналежності функції парності (на boolean circuits) до експоненціального класу складності
1995 Ніл Іммерман, Роберт Шелепчені (Neil Immerman, Rbert Szelepcsnyi) за теорему Іммерман - Шелепчені ( теорія складності обчислень)
1996 Марк Джеррам, Елістер Сінклер (Mark Jerrum, Alistair Sinclair) за дослідження ланцюгів Маркова та апроксимацію перманенту матриць
1997 Джозеф Хелперн, Йорам Мосес (Joseph Halpern, Yoram Moses) за формальне визначення поняття "знання" в розподілених середовищах
1998 Сейносуке Тода (Seinosuke Toda) за теорему Тода, яка показала зв'язок між класами складності PP і PH
1999 Пітер Шор (Peter Shor) за алгоритм Шора для факторизації чисел за полиномиальное кількість часу на квантовому комп'ютері
2000 Мойше Варді, П'єр Вольпер (Moshe Y. Vardi, Pierre Wolper) за дослідження перевірки моделей за допомогою кінцевих автоматів
2001 Санджая Арора, Уріель Фейга, Шафі Гольдвассер, Карстен Лунд, Ласло Ловас, Раджив Мотвані, Шмуель Сафра, Мадху Судан і Маріо Шегеда (Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, Lszl Lovsz, Rajeev Motwani, Shmuel Safra, Madhu Sudan, Mario Szegedy) за теорему PCP і її додаток
2002 Джеро Сенізергуес (Graud Snizergues) за доказ разрешимости еквівалентності детермінованих автоматів з магазинною пам'яттю
2003 Йоав Фрейнд і Роберт Шапіро (Yoav Freund, Robert Schapire) за алгоритм AdaBoost
2004 Моріс Херліхі, Майк Сакс, Нір Шавіт і Фотіос Захароглу (Maurice Herlihy, Mike Saks, Nir Shavit, Fotios Zaharoglou) за додаток топології в теорії розподілених обчислень
2005 Нога Алон, Йоссі Матіас, Маріо Шегеда (Noga Alon, Yossi Matias, Mario Szegedy) за основоположні дослідження у галузі потокових алгоритмів
2006 Маніндра Агравал, Нірадж Кайал, Нітін Саксена (Manindra Agrawal, Neeraj Kayal, Nitin Saxena) за тест Агравал - Каяла - Сакса
2007 Олександр розбору, [2] Стівен Рудик (Alexander Razborov, Steven Rudich) за "природні докази" [3]
2008 Шангуа Тенг, Деніел Спілмен, Стівен Рудик (Shanghua Teng, Daniel Spielman, Steven Rudich) за "згладжений аналіз" алгоритмів
2009 Омер Рейнгольд, Саліл Вадхан, Аві Вігдерсон (Omer Reingold, Salil Vadhan, Avi Wigderson) за зиг-заг-твір графів (англ.) і знаходження логарифмічного по пам'яті детермінованого алгоритму розв'язання задачі неориентированной st-зв'язності (англ.)
2010 Санджая Арора, Джозеф Мітчелл (Sanjeev Arora, Joseph SB Mitchell) за відкриття полиномиальной за часом наближеною схеми (PTAS) для евклідової задачі комівояжера
2011 Йохан Хостад (Johan Hstad) за доказ неаппроксіміруемості для різних комбінаторних задач
2012 Еліас Коутсоупіас (Elias Koutsoupias), Христос Пападімітріу, Тім Роухгарден (Tim Roughgarden), Ева Тардос (va Tardos), Ноам Нісан (Noam Nisan), і Амір Ронен (Amir Ronen) за внесок у розуміння того, як егоїстичне поведінка користувачів і постачальників послуг впливає на поведінку Інтернету та інших складних обчислювальних систем.

Примітки

  1. Премія Геделя - www.csin.ru / info / godel-prize
  2. "Олександр розбору - лауреат премії Геделя 2007" - www.csin.ru/blog/2007-09-03-aleksandr-razborov-laureat-premii-gedelya-2007/, CSIN.ru
  3. http://www.mi.ras.ru/ ~ razborov / int.ps - www.mi.ras.ru/ ~ razborov / int.ps (Англ.)