Премия Гёделя

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Премия Гёделя (англ. Gödel Prize) — премия в области теории вычислительных систем имени Курта Гёделя, вручаемая ежегодно организациями ACM SIGACT[en], Special Interest Group on Algorithms and Computation Theory) и EATCS[en], European Association for Theoretical Computer Science) за выдающиеся труды по логике и теоретической информатике.

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

Лауреаты[править | править код]

Год Имя Примечания
1993 Ласло Бабаи, Шафи Гольдвассер, Сильвио Микали, Шломо Моран и Чарльз Ракофф[en] за разработку интерактивных систем доказательств.
1994 Йохан Хостад[en] за доказательство экспоненциальной нижней оценки на подсчёт четности при помощи булевых схем константной глубины.
1995 Нил Иммерман[en], Роберт Шелепченьи[en] за теорему Иммермана — Шелепченьи (теория сложности вычислений).
1996 Марк Джеррам[en], Элистер Синклер[en] за исследования цепей Маркова и аппроксимацию перманента матриц.
1997 Джозеф Хэлперн[en], Йорам Мозес за формальное определение понятия «знание» в распределённых средах.
1998 Сэйносукэ Тода[en] за теорему Тода, которая показала связь между классами сложности PP и PH.
1999 Питер Шор за алгоритм Шора для факторизации чисел за полиномиальное количество времени на квантовом компьютере.
2000 Мойше Варди[en], Пьер Вольпер[en] за исследование проверки моделей с помощью конечных автоматов.
2001 Санджив Арора[en], Уриэль Фейге, Шафи Гольдвассер, Карстен Лунд[en], Ласло Ловас, Раджив Мотвани, Шмуель Сафра[en], Мадху Судан[en] и Марио Сегеди[en] за теорему PCP и её приложение.
2002 Жеро Сенизерг[en] за доказательство разрешимости эквивалентности детерминированных автоматов с магазинной памятью.
2003 Йоав Фройнд[en] и Роберт Шапире[en] за алгоритм AdaBoost.
2004 Морис Херлихи[en], Майк Сакс[en], Нир Шавит[en] и Фотиос Захароглу[en] за приложение топологии в теории распределённых вычислений.
2005 Нога Алон, Йосси Матиас[en], Марио Сегеди[en] за основополагающие исследования в области потоковых алгоритмов.
2006 Маниндра Агравал[en], Нирадж Кайал[en], Нитин Саксена[en] за тест Агравала — Каяла — Саксены.
2007 Александр Разборов, Стивен Рудич[en] за «естественные доказательства»[1].
2008 Тэн Шанхуа[en], Дэниэл Спилмен за «сглаженный анализ» алгоритмов.
2009 Омер Рейнгольд[en], Салил Вадхан[en], Ави Вигдерсон за зигзаг-произведение графов и нахождение логарифмического по памяти детерминированного алгоритма решения задачи неориентированной st-связности (англ.).
2010 Санджив Арора[en], Джозеф Митчелл[en] за открытие полиномиальной по времени приближённой схемы (PTAS) для евклидовой задачи коммивояжёра.
2011 Йохан Хостад[en] за доказательство неаппроксимируемости для различных комбинаторных задач.
2012 Элиас Куцупиас[fr], Христос Пападимитриу, Тим Роухгарден[en], Эва Тардош, Ноам Нисан[en] и Амир Ронен[fr] за вклад в понимание того, как эгоистичное поведение пользователей и поставщиков услуг влияет на поведение Интернета и других сложных вычислительных систем.
2013 Антуан Жу[en], Дэн Бонех, Мэтью К. Франклин[en] за работы по криптографии[2][3].
2014 Роналд Фэгин[en], Амнон Лотем[fr], Мони Наор[en] за алгоритмы оптимальной агрегации для Middleware[4].
2015 Дэниэл Спилмен, Шангхуа Тенг[en] за серию работ о быстром решении систем линейных уравнений[5].
2016 Стивен Брукс[fr], Питер О'Хёрн[en] за разработку многопоточной сепарационной логики[6].
2017 Cynthia Dwork[en], Frank McSherry[fr], Kobbi Nissim[fr] и Adam D. Smith[fr] Дифференциальная приватность[7].
2018 Одед Регев[fr] Обучение с ошибками[8].

См. также[править | править код]

Примечания[править | править код]

Ссылки[править | править код]