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