Год |
Имя |
Примечания |
1993 | Ласло Бабаи, Шафи Гольдвассер, Сильвио Микали, Шломо Моран и Чарльз Ракофф[en] | за разработку интерактивных систем доказательств. |
1994 | Йохан Хостад[en] | за доказательство экспоненциальной нижней оценки на подсчёт четности при помощи булевых схем константной глубины. |
1995 | Нил Иммерман[en], Роберт Шелепченьи[en] | за теорему Иммермана — Шелепченьи (теория сложности вычислений). |
1996 | Марк Джеррам[en], Элистер Синклер[en] | за исследования цепей Маркова и аппроксимацию перманента матриц. |
1997 | Джозеф Хэлперн[en], Йорам Мозес | за формальное определение понятия «знание» в распределённых средах. |
1998 | Сэйносукэ Тода[en] | за теорему Тода, которая показала связь между классами сложности PP и PH. |
1999 | Питер Шор | за алгоритм Шора для факторизации чисел за полиномиальное количество времени на квантовом компьютере. |
2000 | Моше Варди, Пьер Вольпер[en] | за исследование проверки моделей с помощью конечных автоматов. |
2001 | Санджив Арора[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 | Синтия Дворк, Frank McSherry[fr], Kobbi Nissim[fr] и Adam D. Smith[fr] | Дифференциальная приватность[7]. |
2018 | Одед Регев[fr] | Обучение с ошибками[8]. |