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