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