Виджай Виркумар Вазирани ( хинди : विजय वीरकुमार वज़ीरानी ; род. 1957 [1] ) — заслуженный профессор компьютерных наук индийского происхождения в Школе информатики и компьютерных наук Дональда Брена при Университете США. Калифорния, Ирвин .
Вазирани сначала специализировался на электротехнике в Индийском технологическом институте в Дели, но на втором курсе перевелся в Массачусетский технологический институт и получил степень бакалавра в области компьютерных наук в Массачусетском технологическом институте в 1979 году и степень доктора философии в Калифорнийском университете в Беркли в 1983 году. Его диссертация «Максимальные совпадения без цветков » была защищена Мануэлем Блюмом . [2] После постдокторских исследований с Майклом О. Рабином и Лесли Валиант в Гарвардском университете он присоединился к преподавательскому составу Корнелльского университета в 1984 году. Он перешел в ИИТ Дели в качестве штатного профессора в 1990 году и снова перешел в Технологический институт Джорджии в 1995 году. Он также был приглашенным профессором Маккея в Калифорнийском университете в Беркли и почетным посетителем SISL в Лаборатории социальных и информационных наук Калифорнийского технологического института . В 2017 году он перешел в Калифорнийский университет в Ирвайне в качестве почетного профессора.
Научная карьера Вазирани была сосредоточена вокруг разработки алгоритмов , а также работы над теорией сложности вычислений , криптографией и алгоритмической теорией игр .
В 1980-х годах он внес основополагающий вклад в классическую задачу максимального соответствия [3] и некоторые ключевые вклады в теорию вычислительной сложности , например, лемму изоляции , теорему Вэлианта-Вазирани и эквивалентность между случайной генерацией и приближенным подсчетом. [4] В 1990-х годах он работал в основном над алгоритмами аппроксимации , отстаивая прямо-двойственную схему, которую он применял к проблемам, возникающим при проектировании сетей, размещении объектов [5] , веб-кэшировании и кластеризации. В июле 2001 года он опубликовал книгу, которую широко считают окончательной книгой по алгоритмам аппроксимации (Springer-Verlag, Берлин). С 2002 года он находится на переднем крае усилий по пониманию вычислимости рыночных равновесий, с обширным объемом работ по этой теме.
Результаты его исследований также включают доказательство, совместно с Лесли Валиантом , что если UNIQUE-SAT находится в P , то NP = RP ( теорема Валианта–Вазирани ), и получение в 1980 году, совместно с Сильвио Микали , алгоритма для поиска максимальных соответствий в общих графах; последний до сих пор является наиболее эффективным известным алгоритмом для этой задачи. Совместно с Мехтой, Сабери и Умешем Вазирани он показал в 2007 году, как сформулировать задачу выбора рекламы для AdWords как задачу онлайн- соответствия, и нашел решение этой задачи с оптимальным конкурентным соотношением . [6]
В 2005 году Вазирани и его брат Умеш Вазирани (также учёный-теоретик в области информатики из Калифорнийского университета в Беркли ) были избраны членами Ассоциации вычислительной техники . [7] [8] В 2011 году ему была присуждена стипендия Гуггенхайма .
В 2022 году Вазирани получил премию Джона фон Неймана за «фундаментальный и устойчивый вклад в разработку алгоритмов, включая алгоритмы аппроксимации, теорию сложности вычислений и алгоритмическую теорию игр, занимающую центральное место в исследовании операций и науках управления» [9] .
