Вадхан, Салил
Салил Вадхан
- Гражданство
- США
- Род деятельности
- Теория вычислительной сложности, Криптография
- Место работы
- Гарвардский университет
Награды и премии
Салил Вадхан (англ. Salil Vadhan; [Нет даты!]) — американский учёный в области информатики. Профессор информатики и прикладной математики в Гарвардском университете[1]. Известен исследованиями на стыке теории вычислительной сложности и криптографии, в частности работами по псевдослучайности и доказательствам с нулевым разглашением. За работу над зигзагообразным произведением совместно с Омером Рейнгольдом и Ави Вигдерсоном удостоен премии Гёделя (2009)[2].
Биография и карьера[править]
В 1995 году получил степень бакалавра математики и информатики в Гарварде. В 1999 году получил степень доктора философии по прикладной математике в Массачусетском технологическом институте под руководством Шафи Гольдвассер[3].
Вклад[править]
Зигзагообразное произведение графов для построения графов-экспандеров[править]
Одним из главных достижений Вадхана является новый тип произведения графов, названный зигзагообразным произведением.
При произведении большого графа с малым результирующий граф наследует размер от большого, степень от малого, а свойства экспансии — от обоих. Итерация позволяет получить простые явные конструкции экспандеров постоянной степени любого размера, начиная с одного экспандера постоянного размера.
Для интуитивного понимания и простого анализа свойств зигзагообразного произведения экспандеры рассматриваются как функции, действующие как распространители «волн энтропии». Они преобразуют распределения вероятностей, в которых энтропия сконцентрирована в одной области, в распределения, где эта концентрация рассеивается. В этих терминах произведение графов обеспечивает конструктивную интерференцию двух таких волн.
Вариант этого произведения может применяться к экстракторам. Это даёт первые явные экстракторы, длина семени которых зависит полилогарифмически только от дефицита энтропии источника (а не от его длины), и которые извлекают почти всю энтропию из источников с высокой мин-энтропией. Эти экстракторы имеют несколько применений, включая первые явные экспандеры постоянной степени, преодолевающие «границу собственных значений».
Вадхан также предложил упрощённый подход[4] к проблеме неориентированной ST-связности после результатов Рейнгольда. Зигзагообразное произведение было использовано в доказательстве Омера Рейнгольда равенства классов SL и L.
Доказательства с нулевым разглашением[править]
В этой области Вадхан использует методы теории сложности для понимания возможностей и ограничений доказательств с нулевым разглашением. В серии статей совместно с Одедом Голдрайхом и Амитом Сахаем было получено понимание класса SZK (задач, обладающих статистическими доказательствами с нулевым разглашением). Они охарактеризовали класс SZK и доказали его замкнутость относительно различных операций. Позднее Вадхан исследовал доказательства с нулевым разглашением за пределами класса SZK.
Экстракторы случайности[править]
Совместно с Лу, Омером Рейнгольдом и Ави Вигдерсоном Вадхан создал первые конструкции экстракторов случайности, оптимальные с точностью до постоянных множителей.
Совместно с Тревизаном, Цукерманом, Кампом и Рао он разработал теорию извлечения случайности (и сжатия данных) из сэмплируемых источников — случайных источников, генерируемых эффективным алгоритмом.
Признание[править]
В 2018 году Вадхан был избран членом Ассоциации вычислительной техники (ACM) за «развитие теории вычислительной сложности и криптографии, а также за содействие общественной поддержке теоретической информатики»[5].
Примечания[править]
- ↑ Harvard faculty directory.
- ↑ 2009 Gödel Prize, Европейская ассоциация теоретической информатики.
- ↑ Шаблон:Mathgenealogy.
- ↑ Rozenman-Vadhan.
- ↑ 2018 ACM Fellows Honored for Pivotal Achievements that Underpin the Digital Age. Ассоциация вычислительной техники (2018-12-05). Проверено 15 сентября 2026.
 | Одним из источников, использованных при создании данной статьи, является статья из википроекта «Рувики» («ruwiki.ru») под названием «Вадхан, Салил», расположенная по адресу:
Материал указанной статьи полностью или частично использован в Циклопедии по лицензии CC-BY-SA 4.0 и более поздних версий. Всем участникам Рувики предлагается прочитать материал «Почему Циклопедия?». |
|---|
- Персоналии по алфавиту
- Преподаватели Гарвардского университета
- Учёные в области информатики США
- Выпускники Гарвардского колледжа
- Выпускники Массачусетского технологического института
- Лауреаты премии Гёделя
- Действительные члены Ассоциации вычислительной техники
- Simons Investigators
- Выпускники Школы наук Массачусетского технологического института