Виджай Вазирани - Vijay Vazirani

Виджай Вазирани
Виджей Вазирани.jpg
Виджей Вазирани в 2010 году посетил Калифорнийский университет в Беркли .
Родился 1957 г.
Национальность Американец
Альма-матер MIT (степень бакалавра)
Калифорнийский университет в Беркли (PhD)
Гарвардский университет (PostDoc)
Награды
Научная карьера
Поля алгоритмы , теория сложности вычислений , алгоритмическая теория игр .
Учреждения
Докторант Мануэль Блюм
Докторанты

Виджей Virkumar Вазирани ( хинди : विजय वीरकुमार वज़ीरानी ., Б 1957) является индийский американский выдающийся профессор информатики в Дональд Брен школа информации и компьютерных наук в Университете Калифорнии в Ирвине .

Образование и карьера

Вазирани изучал электротехнику в Индийском технологическом институте в Дели, но после второго курса перешел в Массачусетский технологический институт и получил степень бакалавра компьютерных наук в Массачусетском технологическом институте в 1979 году и докторскую степень. из Калифорнийского университета в Беркли в 1983 году. Его диссертацию « Максимальное совпадение без цветков» возглавлял Мануэль Блюм . После докторантуры с Майклом О. Рабином и Лесли Валиантом в Гарвардском университете он поступил на факультет Корнельского университета в 1984 году. В 1990 году он перешел в ИИТ Дели в качестве профессора, а в 1995 году снова перешел в Технологический институт Джорджии . Он также был приглашенным профессором Маккея в Калифорнийском университете в Беркли и почетным посетителем SISL в лаборатории социальных и информационных наук Калифорнийского технологического института . В 2017 году он перешел в Калифорнийский университет в Ирвине в качестве заслуженного профессора.

Исследовать

Исследовательская карьера Вазирани была сосредоточена вокруг разработки алгоритмов , наряду с работой по теории сложности вычислений , криптографии и теории алгоритмических игр .

В течение 1980-х годов он внес плодотворный вклад в классическую задачу максимального согласования и несколько ключевых вкладов в теорию вычислительной сложности , например, лемму об изоляции , теорему Валианта-Вазирани и эквивалентность между случайной генерацией и приближенным счетом. В течение 1990-х он работал в основном над алгоритмами аппроксимации , отстаивая первично-двойную схему, которую он применял к проблемам, возникающим при проектировании сети, размещении объектов, веб-кэшировании и кластеризации. В июле 2001 г. он опубликовал книгу, которую многие считают исчерпывающей по алгоритмам аппроксимации (Springer-Verlag, Берлин). С 2002 года он был в авангарде попыток понять вычислимость рыночного равновесия, выполнив обширную работу по этой теме.

Его результаты исследования также включают доказательство, наряду с Лесли Валиантом , что если UNIQUE-SAT находится в P , то NP = RP ( теорема Валианта – Вазирани ), и получение в 1980 году вместе с Сильвио Микали алгоритма для поиска максимального соответствия в целом графики; последний по-прежнему является наиболее эффективным известным алгоритмом решения проблемы. Вместе с Мехтой, Сабери и Умешем Вазирани он показал в 2007 году, как сформулировать проблему выбора рекламных объявлений для AdWords как проблему онлайн- сопоставления, и нашел решение этой проблемы с оптимальным коэффициентом конкуренции .

Награды и отличия

В 2005 году и Вазирани, и его брат Умеш Вазирани (также ученый-теоретик из Калифорнийского университета в Беркли ) были приняты в члены Ассоциации вычислительной техники . В 2011 году он был удостоен стипендии Гуггенхайма .

Смотрите также

использованная литература

  1. ^ Deutsche Nationalbibliothek
  2. ^ Виджай Вазирани на Математическая генеалогия
  3. ^ Три из его статей на эту тему с того периода времени имеют более 100 ссылок каждый, согласно Google Scholar: Микали, S. ; Вазирани, В.В. (1980), " Алгоритм поиска максимального соответствия в общих графах", Proc. 21-й симпозиум IEEE. Основы информатики и вычислительной техники ., Стр 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. ^ Джеррам, Марк Р .; Valiant, Лесли Дж .; Вазирани, Виджай В. (1986), «Случайная генерация комбинаторных структур из равномерного распределения», Теоретическая информатика , 43 (2–3): 169–188, DOI : 10.1016 / 0304-3975 (86) 90174-X , Руководство по ремонту  0855970. См. Bubley, Russ (2001), Рандомизированные алгоритмы: аппроксимация, генерация и подсчет , Выдающиеся диссертации CPHC / BCS, Springer-Verlag, p. 120, DOI : 10.1007 / 978-1-4471-0695-1 , ISBN 1-85233-325-1, MR  1986183; Голдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива , Cambridge University Press, стр. 229, ISBN 9781139472746.
  5. ^ Джайн, Камаль; Вазирани, Виджай В. (2001), «Приближенные алгоритмы для метрики местоположения объекта и к-медиана проблем с использованием изначальную-двойной схемы и Лагранжа релаксации», Журнал ACM , 48 (2): 274-296, DOI : 10,1145 / 375827.375845 , МР  1868717 , S2CID  2353092. См. Уильямсон, Дэвид П .; Шмойс, Дэвид Б. (2011), Дизайн аппроксимационных алгоритмов , Cambridge University Press, стр. 191, ISBN 9781139498173
  6. ^ Мехта, Араньяк; Сабери, Амин; Вазирани, Умеш; Вазирани, Виджай (2007), «AdWords и обобщенное онлайн-сопоставление», Журнал ACM , 54 (5): ст. 22, 19, DOI : 10,1145 / 1284320,1284321 , МР  2359264 , S2CID  8481313
  7. ^ ACM стипендиаты премии: Umesh Вазирани архивации 14 декабря 2007, в Wayback Machine .
  8. ^ ACM стипендиаты премии: Виджай Вазирани архивации 14 декабря 2007, в Wayback Machine .

внешние ссылки