- Премия Гёделя
-
Премия Гёделя (англ. Gödel 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 лет.
Содержание
Лауреаты
Год Имя Примечания 1993 Ласло Бабаи, Шафи Гольдвассер, Сильвио Микали, Шломо Моран и Чарльз Ракофф (László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, Charles Rackoff) за разработку интерактивных систем доказательств 1994 Йохан Хостад (Johan Håstad) за доказательство принадлежности функции чётности (на boolean circuits) к экспоненциальному классу сложности 1995 Нил Иммерман, Роберт Шелепчени (Neil Immerman, Róbert Szelepcsényi) за теорему Иммермана — Шелепчени (теория сложности вычислений) 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, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, Mario Szegedy) за теорему PCP и её приложение 2002 Джеро Сенизергуес (Géraud Sénizergues) за доказательство разрешимости эквивалентности детерминированных автоматов с магазинной памятью 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 S. B. Mitchell) за открытие полиномиальной по времени приближённой схемы (PTAS) для евклидовой задачи коммивояжёра 2011 Йохан Хостад (Johan Håstad) за доказательство неаппроксимируемости для различных комбинаторных задач 2012 Элиас Коутсоупиас (Elias Koutsoupias), Христос Пападимитриу, Тим Роухгарден (Tim Roughgarden), Эва Тардос (Éva Tardos), Ноам Нисан (Noam Nisan), и Амир Ронен (Amir Ronen) за вклад в понимание того, как эгоистичное поведение пользователей и поставщиков услуг влияет на поведение Интернета и других сложных вычислительных систем. Примечания
См. также
Ссылки
- Премия Гёделя на сайте ACM SIGACT (англ.)
Категории:- Премии в области информатики
- Лауреаты премии Гёделя
Wikimedia Foundation. 2010.
