Vijay Vazirani

Vijay Vazirani received his Bachelor's degree from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. He is currently Distinguished Professor at the University of California, Irvine.
Vazirani's research career has been centered around the design of algorithms, together with work on computational complexity theory and algorithmic game theory.

Over the years, he has made several seminal contributions to the classical maximum matching problem, studying it from several different computational viewpoints, including worst case analysis, parallel algorithms and online algorithms. He has also made key contributions to computational complexity theory, e.g., the isolation lemma and the Valiant-Vazirani theorem. 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 (Springer-Verlag, Berlin). 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.