Салил Вадхан — американский учёный-компьютерщик. Он является профессором компьютерных наук и прикладной математики имени Вики Джозефа в Гарвардском университете . [1] После получения степени бакалавра по математике и компьютерным наукам в Гарварде в 1995 году он получил докторскую степень по прикладной математике в Массачусетском технологическом институте в 1999 году, где его научным руководителем был Шафи Голдвассер . [2] Его исследования сосредоточены вокруг интерфейса между теорией вычислительной сложности и криптографией . Он фокусируется на темах псевдослучайности и доказательств с нулевым разглашением . Его работа над произведением зигзаг , совместно с Омером Рейнгольдом и Ави Вигдерсоном , была удостоена премии Гёделя 2009 года . [3]
Одним из главных достижений его работы является новый тип графического произведения, называемый зигзагообразным произведением .
Взяв произведение большого графа с малым графом, полученный граф наследует (примерно) свой размер от большого, свою степень от малого и свои свойства расширения от обоих. Итерация дает простые явные конструкции экспандеров постоянной степени каждого размера, начиная с одного экспандера постоянного размера.
Решающее значение для интуиции и простого анализа свойств зигзагообразного произведения имеет представление о расширителях как функциях, которые действуют как пропагаторы "волны энтропии" — они преобразуют распределения вероятностей, в которых энтропия сосредоточена в одной области, в распределения, в которых эта концентрация рассеивается. В этих терминах графовое произведение допускает конструктивную интерференцию двух таких волн.
Вариант этого продукта может быть применен к экстракторам, давая первые явные экстракторы, длина семени которых зависит (поли)логарифмически только от дефицита энтропии источника (а не от его длины) и которые извлекают почти всю энтропию источников с высокой минимальной энтропией. Эти экстракторы с высокой минимальной энтропией имеют несколько интересных приложений, включая первые явные расширители постоянной степени, которые превосходят «границу собственных значений».
Вадхан также предложил другой упрощенный подход [4] к проблеме ненаправленной ST-связности после прорывного результата Рейнгольда. Также зигзагообразное произведение было полезно в доказательстве Омера Рейнгольда того , что SL = L.
Его работа в этой области заключается в использовании методов теории сложности для понимания силы и ограничений доказательств с нулевым разглашением. В серии статей с Одедом Голдрайхом и Амитом Сахаем они получили полное понимание класса SZK проблем, обладающих статистическими доказательствами с нулевым разглашением, охарактеризовали класс SZK и доказали, что SZK замкнут относительно различных операций. Недавно его работа была попыткой работать над доказательством с нулевым разглашением за пределами класса SZK.
Совместно с Лу, Омером Рейнгольдом и Ави Вигдерсоном он разработал первую конструкцию экстракторов случайности , которые являются «оптимальными с точностью до постоянных множителей», достигнув важной вехи в десятилетней работе над этой темой.
Совместно с Тревизаном, Цукерманом, Кампом и Рао он разработал теорию извлечения случайности (и сжатия данных) из выборочных источников, которые представляют собой случайные источники, генерируемые (неизвестным) эффективным алгоритмом.
В 2018 году Вадхан был избран членом ACM за «продвижение вычислительной сложности и криптографии, а также за содействие общественной поддержке теоретической информатики». [5]