Vijay Vazirani

US-amerikanischer Informatiker

Vijay Virkumar Vazirani (* 20. April 1957) ist ein indischstämmiger US-amerikanischer Informatiker.

Vijay Vazirani, 2010, University of California, Berkeley.

Vazirani studierte am Massachusetts Institute of Technology (Bachelor-Abschluss 1979) und promovierte 1983 an der University of California, Berkeley bei Manuel Blum (Maximum matchings without blossoms). In den 1990er Jahren war er Professor am Indian Institute of Technology in Delhi. Er war Professor für Informatik am Georgia Institute of Technology. Er war unter anderem Gastprofessor in Berkeley. Seit 2017 ist er Professor an der University of California, Irvine.

Vazirani beschäftigte sich mit der Entwicklung von Approximations-Algorithmen (wie Jain-Vazirani Algorithmus in der Facility Location 2001), Paarungs-Algorithmen (Matching) in der Graphentheorie (mit Silvio Micali fand er 1980 einen verbesserten Algorithmus für maximale Paarungen in Graphen)[1], Komplexitätstheorie (wo er mit Leslie Valiant 1985 ein wichtiges Theorem bewies), Kryptographie, Codierungstheorie, algorithmischer Spieltheorie sowie Quanten-Informatik.

2022 erhielt Vazirani den John-von-Neumann-Theorie-Preis.

Sein Bruder Umesh Vazirani ist Informatik-Professor in Berkeley. Beide sind seit 2005 Fellows der Association for Computing Machinery (ACM).

Sein Vater V.N. Vazirani war Professor für Bauingenieurwesen.

Schriften

Bearbeiten
  • Approximation algorithms, Springer 2001
  • mit Noam Nisan, Éva Tardos, Tim Roughgarden (Herausgeber): Algorithmic Game Theory, Cambridge University Press 2007
Bearbeiten

Einzelnachweise

Bearbeiten
  1. Vazirani, Micali An   algorithm for finding maximum matching in general graphs, Proc. 21. IEEE Symposium Foundations Computer Science, 1980, S. 17–27 (|V|= Anzahl Ecken, |E|= Anzahl Kanten)