Премия Гёделя | это... Что такое Премия Гёделя? (original) (raw)
Премия Гёделя (англ. 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) | за вклад в понимание того, как эгоистичное поведение пользователей и поставщиков услуг влияет на поведение Интернета и других сложных вычислительных систем. |
Примечания
- ↑ Премия Геделя
- ↑ «Александр Разборов — лауреат премии Геделя 2007», CSIN.ru
- ↑ http://www.mi.ras.ru/~razborov/int.ps (англ.)
См. также
Ссылки
- Премия Гёделя на сайте ACM SIGACT (англ.)