Виджай Виркумар Вазирани ( хинди : विजय वीरकुमार वज़ीरानी ; б . _ _
Вазирани сначала специализировался в области электротехники в Индийском технологическом институте в Дели, но на втором курсе он перешел в Массачусетский технологический институт и получил степень бакалавра компьютерных наук в Массачусетском технологическом институте в 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]
