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

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

Виджай Виркумар Вазирани (хинди: विजय वीरकुमार वज़ीरानी; б. 1957 г.[1]) является Индийский американец заслуженный профессор информатики в Школа информации и компьютерных наук Дональда Брена на Калифорнийский университет в Ирвине.

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

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

Исследование

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

В 80-е годы он внес значительный вклад в развитие классической музыки. максимальное соответствие проблема,[3] и некоторые ключевые вклады в теория сложности вычислений, например, лемма об изоляции, то Теорема Валианта-Вазирани, а также эквивалентность случайной генерации и приблизительного подсчета.[4] В 1990-е годы он в основном работал над аппроксимационные алгоритмы, отстаивая первично-дуальную схему, которую он применял к проблемам, возникающим при проектировании сети, размещении объектов[5] и веб-кеширование, и кластеризация. В июле 2001 года он опубликовал то, что многие считают окончательной книгой по аппроксимационные алгоритмы (Шпрингер-Верлаг, Берлин). С 2002 года он был в авангарде попыток понять вычислимость рыночного равновесия, выполнив обширную работу по этой теме.

Его результаты исследования также включают доказательства, наряду с Лесли Валиант, что если УНИКАЛЬНО-СБ в п, тогда НП = RP (Теорема Вэлианта – Вазирани ), и получив в 1980 г. вместе с Сильвио Микали, алгоритм поиска максимального совпадения в общих графах; последний по-прежнему является наиболее эффективным из известных алгоритмов решения проблемы. С помощью Мехты, Сабери и Умеш Вазирани в 2007 году он показал, как сформулировать задачу выбора рекламы для AdWords как онлайн проблема соответствия, и нашли решение этой проблемы с оптимальным конкурентное соотношение.[6]

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

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

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

Рекомендации

  1. ^ Deutsche Nationalbibliothek
  2. ^ Виджай Вазирани на Проект "Математическая генеалогия"
  3. ^ По словам ученого Google, три его работы по этой теме того времени имеют более 100 цитирований каждая: Микали, С.; Вазирани, В. В. (1980), "Ан алгоритм поиска максимального совпадения в общих графах », Proc. 21-й симпозиум IEEE. Основы информатики, стр. 17–27, Дои:10.1109 / SFCS.1980.12, S2CID  27467816; Малмулей, Кетан; Вазирани, Умеш В.; Вазирани, Виджай В. (1987), «Сопоставление так же просто, как и обращение матрицы», Комбинаторика, 7 (1): 105–113, Дои:10.1007 / BF02579206, S2CID  47370049; Карп, Ричард М.; Вазирани, Умеш В .; Вазирани, Виджай В. (1990), "Оптимальный алгоритм он-лайн двустороннего сопоставления", Proc 22nd ACM Symp. Теория вычислений, стр. 352–358, Дои:10.1145/100216.100262, ISBN  0-89791-361-2, S2CID  822904.
  4. ^ Jerrum, Mark R .; Valiant, Лесли Дж .; Вазирани, Виджай В. (1986), "Случайная генерация комбинаторных структур из равномерного распределения", Теоретическая информатика, 43 (2–3): 169–188, Дои:10.1016 / 0304-3975 (86) 90174-Х, МИСТЕР  0855970. Видеть Бублей, Русь (2001), Рандомизированные алгоритмы: аппроксимация, генерация и подсчет, Выдающиеся диссертации CPHC / BCS, Springer-Verlag, p. 120, Дои:10.1007/978-1-4471-0695-1, ISBN  1-85233-325-1, МИСТЕР  1986183; Гольдрайх, Одед (2008), Вычислительная сложность: концептуальная перспектива, Cambridge University Press, стр. 229, ISBN  9781139472746.
  5. ^ Джайн, Камаль; Вазирани, Виджай В. (2001), «Алгоритмы аппроксимации для метрического определения местоположения объекта и задач k-медианы с использованием первично-дуальной схемы и лагранжевой релаксации», Журнал ACM, 48 (2): 274–296, Дои:10.1145/375827.375845, МИСТЕР  1868717, S2CID  2353092. Видеть Уильямсон, Дэвид П .; Шмойс, Дэвид Б. (2011), Дизайн аппроксимационных алгоритмов, Cambridge University Press, стр. 191, г. ISBN  9781139498173
  6. ^ Мехта, Араньяк; Сабери, Амин; Вазирани, Умеш; Вазирани, Виджай (2007), «AdWords и обобщенное онлайн-сопоставление», Журнал ACM, 54 (5): Ст. 22, 19, Дои:10.1145/1284320.1284321, МИСТЕР  2359264, S2CID  8481313
  7. ^ Награда стипендиатов ACM: Умеш Вазирани В архиве 14 декабря 2007 г. Wayback Machine.
  8. ^ Награда стипендиатов ACM: Виджай Вазирани В архиве 14 декабря 2007 г. Wayback Machine.

внешняя ссылка