Элдер Шафир

Элдер Шафир — это израильский и американский математик, специализирующийся в области теоретической информатики, комбинаторики и теории сложности вычислений. Наиболее известен своими работами в области дерандомизации, теории кодирования, комбинаторной теории игр и, в частности, за доказательство гипотезы о чувствительности булевых функций (2019).

Биография

Элдер Шафир родился в 1966 году в Израиле. Получил степень бакалавра по математике и информатике в Еврейском университете в Иерусалиме (1986). В 1991 году под руководством Ави Вигдерсона получил степень доктора философии (Ph.D.) по информатике в Еврейском университете. После защиты диссертации работал в Институте перспективных исследований (IAS) в Принстоне, а затем в Корнеллском университете. С 1996 года является профессором Принстонского университета (США). Помимо академической деятельности, занимал должность главного учёного (Chief Scientist) в компании Microsoft Research New England (2013–2016).

Основные научные достижения

Доказательство гипотезы о чувствительности (2019)

Наиболее известное достижение Шафира — доказательство гипотезы о чувствительности булевых функций, которая оставалась нерешённой в течение почти 30 лет. Гипотеза, впервые сформулированная в 1990-х годах, утверждает, что для любой булевой функции её чувствительность (минимальное количество входных битов, изменение которых меняет значение функции) связана с её блоковой чувствительностью. Шафир представил элегантное и короткое (около 10 страниц) доказательство, использующее методы линейной алгебры и комбинаторики. Это доказательство было опубликовано в журнале Annals of Mathematics в 2021 году и признано одним из важнейших результатов в области теории сложности за последние десятилетия.

Работы в области дерандомизации

Шафир внёс фундаментальный вклад в теорию дерандомизации — преобразования вероятностных алгоритмов в детерминированные. Совместно с Ави Вигдерсоном разработал метод построения псевдослучайных генераторов для схем ограниченной глубины (AC0), что позволило доказать, что задачи, решаемые такими схемами, могут быть эффективно дерандомизированы. Эта работа заложила основы современной теории псевдослучайности.

Теория кодирования и комбинаторика

Шафир известен работами в области теории кодирования, в частности, по построению локально декодируемых кодов (LDC) и кодов с исправлением ошибок. Он также внёс вклад в комбинаторную теорию игр и теорию графов, включая изучение свойств случайных графов и графов-экспандеров.

Другие результаты

• Сложность приближённых вычислений: совместно с Уриэлем Фейге и др. доказал, что задача о максимальной клике не может быть аппроксимирована с полиномиальной точностью, если P ≠ NP.
• Теория игр: разработал метод «сглаживания» (smoothing) для анализа комбинаторных игр, который нашёл применение в экономике и теории аукционов.
• Алгоритмы для потоковых данных: совместно с Питером Индиком и др. разработал алгоритмы для оценки частот элементов в потоковых данных (алгоритм Count-Min Sketch).

Награды и признание

• Премия Гёделя (2009) — за фундаментальные работы в области дерандомизации и псевдослучайности (совместно с Ави Вигдерсоном).
• Премия Фулкерсона (2021) — за доказательство гипотезы о чувствительности.
• Член Американской академии искусств и наук (с 2020).
• Член Национальной академии наук США (с 2022).
• Приглашённый докладчик на Международном конгрессе математиков (ICM) в 2010 и 2022 годах.

Публикации и лекции

Шафир является автором более 100 научных статей, опубликованных в ведущих рецензируемых журналах и трудах конференций (STOC, FOCS, Journal of the ACM, Annals of Mathematics). Его лекции отличаются ясностью и доступностью изложения сложных математических концепций. Он активно ведёт научно-популярный блог и выступает с публичными лекциями, в том числе в рамках проекта «Quanta Magazine».

Влияние на науку

Работы Шафира оказали значительное влияние на развитие теоретической информатики, особенно в области теории сложности и комбинаторики. Его доказательство гипотезы о чувствительности стало примером того, как простые и элегантные методы могут решать давние открытые проблемы. Многие его результаты (например, метод дерандомизации для AC0) вошли в стандартные учебники по теории вычислений. Шафир также известен как наставник молодых учёных: под его руководством защитили диссертации более 20 аспирантов, многие из которых стали ведущими исследователями в своих областях.

Источники

• Gil Kalai, «The Sensitivity Conjecture», Annals of Mathematics, 2021.
• Avi Wigderson, «Mathematics and Computation», Princeton University Press, 2019.
• Quanta Magazine, «The Simple Math That Solved a 30-Year-Old Computer Science Problem», 2019.
• Princeton University, Faculty Profile: Elad Shafir.
• Gödel Prize 2009 Citation.