| Год
|
Имя
|
Примечания
|
| 1993 |
Ласло Бабаи, Шафи Гольдвассер, Сильвио Микали, Шломо Моран и Чарльз Ракофф[англ.] |
за разработку интерактивных систем доказательств[англ.][2][3].
|
| 1994 |
Йохан Хостад[англ.] |
за доказательство экспоненциальной нижней оценки на подсчёт чётности при помощи булевых схем константной глубины[4][5].
|
| 1995 |
Нил Иммерман[англ.], Роберт Шелепченьи[англ.] |
за теорему Иммермана — Шелепченьи[англ.] (теория сложности вычислений)[6][7].
|
| 1996 |
Марк Джеррам[англ.], Элистер Синклер[англ.] |
за исследования цепей Маркова и аппроксимацию перманента матриц[8][9].
|
| 1997 |
Джозеф Хэлперн[англ.], Йорам Мозес |
за формальное определение понятия «знание» в распределённых средах[10][11].
|
| 1998 |
Сэйносукэ Тода[англ.] |
за теорему Тода[англ.], которая показала связь между классами сложности PP и PH[12][13].
|
| 1999 |
Питер Шор |
за алгоритм Шора для факторизации чисел за полиномиальное количество времени на квантовом компьютере[14][15].
|
| 2000 |
Моше Варди, Пьер Вольпер[англ.] |
за исследование проверки моделей с помощью конечных автоматов[16][17].
|
| 2001 |
Санджив Арора, Уриэль Фейге, Шафи Гольдвассер, Карстен Лунд[англ.], Ласло Ловас, Раджив Мотвани, Шмуель Сафра[англ.], Мадху Судан, Марио Сегеди[англ.] |
за теорему PCP и её приложение[18][19].
|
| 2002 |
Жеро Сенизерг[англ.] |
за доказательство разрешимости эквивалентности детерминированных автоматов с магазинной памятью[20][21].
|
| 2003 |
Йоав Фройнд[англ.] и Роберт Шапире[англ.] |
за алгоритм AdaBoost[22][23].
|
| 2004 |
Морис Херлихи, Майкл Сакс[англ.], Нир Шавит и Фотиос Захароглу |
за приложение топологии в теории распределённых вычислений[24][25].
|
| 2005 |
Нога Алон, Йосси Матиас[англ.], Марио Сегеди[англ.] |
за основополагающие исследования в области потоковых алгоритмов[26][27].
|
| 2006 |
Маниндра Агравал[англ.], Нирадж Кайал[англ.], Нитин Саксена[англ.] |
за тест Агравала — Каяла — Саксены[28][29].
|
| 2007 |
Александр Разборов, Стивен Рудич[англ.] |
за «естественные доказательства»[30][31].
|
| 2008 |
Тэн Шанхуа, Дэниэл Спилмен |
за «сглаженный анализ» алгоритмов[32].
|
| 2009 |
Омер Рейнгольд[англ.], Салил Вадхан[англ.], Ави Вигдерсон |
за зигзаг-произведение графов и нахождение логарифмического по памяти детерминированного алгоритма решения задачи неориентированной st-связности[англ.][33].
|
| 2010 |
Санджив Арора, Джозеф Митчелл[англ.] |
за открытие полиномиальной по времени приближённой схемы (PTAS) для евклидовой задачи коммивояжёра[34].
|
| 2011 |
Йохан Хостад[англ.] |
за доказательство неаппроксимируемости для различных комбинаторных задач[35].
|
| 2012 |
Элиас Куцупиас[фр.], Христос Пападимитриу, Тим Роухгарден[англ.], Эва Тардош, Ноам Нисан[англ.], Амир Ронен[фр.] |
за вклад в понимание того, как эгоистичное поведение пользователей и поставщиков услуг влияет на поведение Интернета и других сложных вычислительных систем[36].
|
| 2013 |
Антуан Жу[англ.], Дэн Боне, Мэтью К. Франклин[англ.] |
за работы по криптографии[37][38].
|
| 2014 |
Роналд Фэгин[англ.], Амнон Лотем[фр.], Мони Наор[англ.] |
за алгоритмы оптимальной агрегации для Middleware[39].
|
| 2015 |
Дэниэл Спилмен, Тэн Шанхуа |
за серию работ о быстром решении систем линейных уравнений[40][41].
|
| 2016 |
Стивен Брукс[фр.], Питер О'Хёрн[англ.] |
за разработку параллельной логики разделения[42].
|
| 2017 |
Синтия Дворк, Фрэнк Макшерри[фр.], Коби Ниссим[фр.], Адам Д. Смит[фр.] |
Дифференциальная приватность[43].
|
| 2018 |
Одед Регев |
Обучение с ошибками[44].
|
| 2019 |
Ирит Динур[45] |
за новое, более простое доказательство теоремы PCP методом увеличения зазора[46].
|
| 2020 |
Робин Мозер[англ.] и Габор Тардос[англ.] |
за алгоритмическую версию локальной леммы Ловаса[47]
|
| 2021 |
Андрей Булатов, Джин-И Цай[англ.], Си Чэнь[англ.], Мартин Дайер[англ.] и Дэвид Ричерби |
за работу по классификации сложности вычислений в задачах по удовлетворению ограничений[48]
|
| 2022 |
Цвика Бракерски[англ.], Крейг Джентри[англ.] и Винод Вайкунтанатан[англ.] |
за новаторский вклад в криптографию при помощи создания схем полностью гомоморфного шифрования[49]
|
| 2023 |
Самуэль Фиорини, Серж Массар[англ.] и Себастьян Покутта, Ханс Радж Тивари, Рональд де Вольф и Томас Ротвосс |
за доказательство того, что любая расширенная формулировка политопа для задачи коммивояжёра имеет экспоненциальный размер[50]
|
| 2024 |
Райан Уильямс |
за его работы по нижним оценкам для схем и парадигму «нижние оценки из алгоритмов»[51]
|
