Vijay Vazirani


Vijay Virkumar Vazirani is an Indian American distinguished professor of computer science in the Donald Bren School of Information and Computer Sciences at the University of California, Irvine.

Education and career

Vazirani received his Bachelor's degree from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. His dissertation, Maximum Matchings without Blossoms, was supervised by Manuel Blum.
After postdoctoral research with Michael O. Rabin and Leslie Valiant at Harvard University, he joined the faculty at Cornell University in 1984. He moved to the Indian Institute of Technology, Delhi as a full professor in 1990, and moved again to the Georgia Institute of Technology in 1995. He was also a McKay Visiting Professor at the University of California, Berkeley, and a Distinguished SISL Visitor at the Social and Information Sciences Laboratory at the California Institute of Technology. In 2017 he moved to the University of California, Irvine as Distinguished Professor.

Research

Vazirani's research career has been centered around the design of algorithms, together with work on computational complexity theory, cryptography, and algorithmic game theory.
During the 1980s, he made seminal contributions to the classical maximum matching problem, and some key contributions to computational complexity theory, e.g., the isolation lemma, the Valiant-Vazirani theorem, and the equivalence between random generation and approximate counting. During the 1990s he worked mostly on approximation algorithms, championing the primal-dual schema, which he applied to problems arising in network design, facility location and web caching, and clustering. In July 2001 he published what is widely regarded as the definitive book on approximation algorithms. Since 2002, he has been at the forefront
of the effort to understand the computability of market equilibria, with an extensive body of work on the topic.
His research results also include proving, along with Leslie Valiant, that if UNIQUE-SAT is in P, then NP = RP, and obtaining in 1980, along with Silvio Micali, an algorithm for finding maximum matchings in general graphs; the latter is still the most efficient known algorithm for the problem.
With Mehta, Saberi, and Umesh Vazirani, he showed in 2007 how to formulate the problem of choosing advertisements for AdWords as an online matching problem, and found a solution to this problem with optimal competitive ratio.

Awards and honors

In 2005 both Vazirani and his brother Umesh Vazirani were inducted as Fellows of the Association for Computing Machinery.
In 2011, he was awarded a Guggenheim Fellowship.