Виджай Вазирани

Виджай Вазирани
Виджай Вазирани
	В Калифорнийском университете в Ирвине , 2021 г.
Рожденный	1957 ; Индия
Национальность	Американский
Альма-матер	MIT (степень бакалавра) ; Калифорнийский университет в Беркли (доктор философии) ; Гарвардский университет (постдок)
Известный	Теорема Валианта–Вазирани , Лемма об изоляции
Родственники	Умеш Вазирани (брат)
Награды	Член ACM ; Стипендия Гуггенхайма ; Премия Джона фон Неймана за теорию ;
	Научная карьера
Поля	алгоритмы , теория сложности вычислений , алгоритмическая теория игр .
Учреждения	Технологический институт Джорджии ; Индийский технологический институт, Дели ; Калифорнийский университет, Ирвин ;
Диссертация	Максимум совпадений без цветения (1985)
Докторантура	Мануэль Блюм
Докторанты	Навин Гарг ; Самир Хуллер ;
Веб-сайт	www .ics .uci .edu /~министр

Виджай Виркумар Вазирани ( хинди : Виджай Виркумар Вазирани ; р. 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]

См. также [ править ]

Список индийских математиков

Ссылки [ править ]

^ Немецкая национальная библиотека
^ Виджай Вазирани в проекте «Математическая генеалогия»
↑ По данным ученого Google, три его статьи на эту тему за тот период времени имеют более 100 цитирований каждая: Микали, С .; Вазирани, В.В. (1980), «Ан $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ алгоритм поиска максимального соответствия в общих графах», Proc. 21st IEEE Symp. Foundations of Computer Science , стр. 17–27, doi : 10.1109/SFCS.1980.12 , S2CID 27467816 ; Малмули, Кетан ; Вазирани, Умеш В. ; Вазирани, Виджей В. (1987), «Сопоставление так же просто, как инверсия матрицы», Combinatorica , 7 (1): 105–113, doi : 10.1007/BF02579206 , S2CID 47370049 ; Карп, Ричард М .; Вазирани, Умеш В.; Вазирани, Виджай В. (1990), «Оптимальный алгоритм для двустороннего сопоставления в режиме онлайн», Proc 22nd ACM Symp. Теория вычислений , стр. 352–358, doi : 10.1145/100216.100262 , ISBN. 0-89791-361-2 , S2CID 822904 .
^ Джеррам, Марк Р.; Валиант, Лесли Г.; Вазирани, Виджай В. (1986), «Случайная генерация комбинаторных структур из равномерного распределения», Theoretical Computer Science , 43 (2–3): 169–188, doi : 10.1016/0304-3975(86)90174-X , МР 0855970 . Видеть Бубли, Расс (2001), Рандомизированные алгоритмы: аппроксимация, генерация и подсчет , CPHC/BCS Distinguished Dissertations, Springer-Verlag, стр. 120, номер домена : 10.1007/978-1-4471-0695-1 , ISBN. 1-85233-325-1 , MR 1986183 , S2CID 266744010 ; Гольдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , издательство Кембриджского университета, стр. 229, ISBN 9781139472746 .
^ Джайн, Камаль; Вазирани, Виджай В. (2001), «Алгоритмы аппроксимации местоположения метрических объектов и задач k-медианы с использованием первично-двойственной схемы и лагранжевой релаксации», Journal of the ACM , 48 (2): 274–296, doi : 10.1145/ 375827.375845 , МР 1868717 , S2CID 2353092 . Видеть Уильямсон, Дэвид П.; Шмойс, Дэвид Б. (2011), Разработка алгоритмов аппроксимации , Cambridge University Press, стр. 191, ИСБН 9781139498173
^ Мехта, Араньяк; Сабери, Амин; Вазирани, Умеш; Вазирани, Виджай (2007), «AdWords и обобщенное онлайн-соответствие», Журнал ACM , 54 (5): Ст. 22, 19, doi : 10.1145/1284320.1284321 , MR 2359264 , S2CID 8481313
↑ Премия ACM Fellows: Умеш Вазирани. Архивировано 14 декабря 2007 года в Wayback Machine .
↑ Премия ACM Fellows: Виджай Вазирани. Архивировано 14 декабря 2007 года в Wayback Machine .
^ «Зал награждений ежегодного собрания INFORMS 2022» . Ежегодное собрание INFORMS 2022 . 5 октября 2022 г. Проверено 8 ноября 2022 г.

Внешние ссылки [ править ]

Домашняя страница Калифорнийского университета в Ирвайне
Публикации Виджая Вазирани, проиндексированные Google Scholar

[1] Немецкая национальная библиотека

[2] Виджай Вазирани в проекте «Математическая генеалогия»

[3] По данным ученого Google, три его статьи на эту тему за тот период времени имеют более 100 цитирований каждая: Микали, С .; Вазирани, В.В. (1980), «Ан $\scriptstyle O({\sqrt {|V|}}\cdot |E|)$ алгоритм поиска максимального соответствия в общих графах», Proc. 21st IEEE Symp. Foundations of Computer Science , стр. 17–27, doi : 10.1109/SFCS.1980.12 , S2CID 27467816 ; Малмули, Кетан ; Вазирани, Умеш В. ; Вазирани, Виджей В. (1987), «Сопоставление так же просто, как инверсия матрицы», Combinatorica , 7 (1): 105–113, doi : 10.1007/BF02579206 , S2CID 47370049 ; Карп, Ричард М .; Вазирани, Умеш В.; Вазирани, Виджай В. (1990), «Оптимальный алгоритм для двустороннего сопоставления в режиме онлайн», Proc 22nd ACM Symp. Теория вычислений , стр. 352–358, doi : 10.1145/100216.100262 , ISBN. 0-89791-361-2 , S2CID 822904 .

[4] Джеррам, Марк Р.; Валиант, Лесли Г.; Вазирани, Виджай В. (1986), «Случайная генерация комбинаторных структур из равномерного распределения», Theoretical Computer Science , 43 (2–3): 169–188, doi : 10.1016/0304-3975(86)90174-X , МР 0855970 . Видеть Бубли, Расс (2001), Рандомизированные алгоритмы: аппроксимация, генерация и подсчет , CPHC/BCS Distinguished Dissertations, Springer-Verlag, стр. 120, номер домена : 10.1007/978-1-4471-0695-1 , ISBN. 1-85233-325-1 , MR 1986183 , S2CID 266744010 ; Гольдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , издательство Кембриджского университета, стр. 229, ISBN 9781139472746 .

[5] Джайн, Камаль; Вазирани, Виджай В. (2001), «Алгоритмы аппроксимации местоположения метрических объектов и задач k-медианы с использованием первично-двойственной схемы и лагранжевой релаксации», Journal of the ACM , 48 (2): 274–296, doi : 10.1145/ 375827.375845 , МР 1868717 , S2CID 2353092 . Видеть Уильямсон, Дэвид П.; Шмойс, Дэвид Б. (2011), Разработка алгоритмов аппроксимации , Cambridge University Press, стр. 191, ИСБН 9781139498173

[6] Мехта, Араньяк; Сабери, Амин; Вазирани, Умеш; Вазирани, Виджай (2007), «AdWords и обобщенное онлайн-соответствие», Журнал ACM , 54 (5): Ст. 22, 19, doi : 10.1145/1284320.1284321 , MR 2359264 , S2CID 8481313

[7] Премия ACM Fellows: Умеш Вазирани. Архивировано 14 декабря 2007 года в Wayback Machine .

[8] Премия ACM Fellows: Виджай Вазирани. Архивировано 14 декабря 2007 года в Wayback Machine .

[9] «Зал награждений ежегодного собрания INFORMS 2022» . Ежегодное собрание INFORMS 2022 . 5 октября 2022 г. Проверено 8 ноября 2022 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Базы данных авторитетного контроля
International	ISNI VIAF WorldCat
National	Norway France BnF data Germany Israel United States Latvia Japan Czech Republic Netherlands Poland
Academics	Association for Computing Machinery CiNii DBLP Google Scholar MathSciNet Mathematics Genealogy Project zbMATH
Other	IdRef