Салил Вадхан - Salil Vadhan

Салил Вадхан
Салил Вадхан.jpg
Салил Вадхан
ГражданствоСоединенные Штаты
Альма-матерГарвардский университет (BA)
Массачусетский Институт Технологий (Доктор философии)
Награды
Научная карьера
ПоляТеория вычислительной сложности, Криптография
УчрежденияГарвардский университет
ДокторантШафи Гольдвассер

Салил Вадхан Вики Джозеф профессор компьютерных наук и прикладной математики в Гарвардский университет.[1] После получения степени бакалавра математики и компьютерных наук в Гарварде в 1995 году он получил докторскую степень по прикладной математике в Массачусетский Институт Технологий в 1999 году, когда его советник был Шафи Гольдвассер.[2] Его исследования сосредоточены на взаимодействии между теория сложности вычислений и криптография. Он фокусируется на темах псевдослучайности и доказательств с нулевым разглашением. Его работа над зигзагообразный продукт, с Омер Рейнгольд и Ави Вигдерсон, был награжден 2009 Премия Гёделя.[3]

Взносы

Зигзагообразный графический продукт для построения расширительных графиков

Одним из основных вкладов его работы является новый тип графического продукта, названный зигзагообразный продукт.

Взяв произведение большого графа на маленький, полученный граф наследует (примерно) свой размер от большого, степень от малого и свойства расширения от обоих. Итерация дает простые явные конструкции расширителей постоянной степени любого размера, начиная с одного расширителя постоянного размера.

Решающее значение для интуиции и простого анализа свойств зигзагообразного продукта имеет взгляд на расширители как на функции, которые действуют как пропагаторы «волны энтропии» - они преобразуют распределения вероятностей, в которых энтропия сосредоточена в одной области, в распределения, в которых эта концентрация равна рассеялся. Таким образом, графическое произведение допускает конструктивную интерференцию двух таких волн.

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

Вадхан также предложил другой упрощенный подход.[4] к неориентированному ST-подключение проблема, следующая за революционным результатом Рейнгольда. Также зигзагообразный продукт был полезен в Омер Рейнгольд доказательство того, что SL =L.

Доказательства с нулевым разглашением

Его работа в этой области заключается в использовании методов теории сложности, чтобы понять силу и ограничения доказательств с нулевым разглашением. В серии статей с Одед Гольдрайх и Амит Сахаи, они получили полное представление о классе SZK задач, обладающих статистическими доказательствами с нулевым разглашением, охарактеризовали класс SZK и доказали, что SZK замкнут относительно различных операций. Недавно его работа была попыткой работать над доказательством с нулевым разглашением за пределами класса SZK.

Экстракторы случайности

С Лу, Омер Рейнгольд, и Ави Вигдерсон, он дал первую конструкцию экстракторы случайности которые являются «оптимальными с точностью до постоянных факторов», что является важной вехой за десятилетие работы над этим предметом.

Вместе с Тревисаном, Цукерманом, Кампом и Рао он разработал теорию извлечения случайности (и сжатия данных) из выборочных источников, которые представляют собой случайные источники, генерируемые (неизвестным) эффективным алгоритмом.

Признание

Вадхан был избран Член ACM в 2018 году за «повышение сложности вычислений и криптографии, а также за содействие общественной поддержке теоретической информатики».[5]

Рекомендации

  1. ^ Каталог факультетов Гарварда.
  2. ^ Салил Вадхан на Проект "Математическая генеалогия".
  3. ^ Премия Гёделя 2009 г., Европейская ассоциация теоретической информатики.
  4. ^ Розенман-Вадхан.
  5. ^ Стипендиаты ACM 2018 награждены за ключевые достижения, лежащие в основе цифровой эпохи, Ассоциация вычислительной техники, 5 декабря 2018

внешняя ссылка