Меню

Главная
Случайная статья
Настройки
Премия Гёделя: различия между версиями
Материал из https://ru.wikipedia.org

Премия Гёделя (англ. 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). Основным требованием к работе является дата первой публикации — к номинации допускаются лишь труды не старше 14 лет.

Содержание

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


См. также

Примечания
  1. Gdel Prize — 2007
  2. Three Papers Cited for Laying Foundation of Growth in Algorithmic Game Theory. 2012-05-16. Архивировано 2013-07-18. Дата обращения: 2012-05-16. {{cite news}}: |archive-date= / |archive-url= несоответствие временной метки; предлагается 18 июля 2013 (справка); Неизвестный параметр |deadurl= игнорируется (|url-status= предлагается) (справка)
  3. Gdel Prize — 2013
  4. ACM Group Presents Gdel Prize for Advances in Cryptography — Association for Computing Machinery Архивировано 1 июня 2013 года.
  5. Goedel Prize 2014
  6. http://www.sigact.org/Prizes/Godel/citation2015.pdf. Дата обращения: 15 января 2017. Архивировано из оригинала 9 декабря 2017 года.
  7. 2016 Gdel Prize
  8. 2017 Gdel Prize. European Association for Theoretical Computer Science. EATCS. Дата обращения: 29 марта 2017.
  9. 2018 Gdel Prize
  10. Knuth and Gdel Prizes to be Awarded at 2019 ACM SIGACT Conference
  11. 2019 Gdel Prize citation.


Ссылки
Downgrade Counter