Bio

A veteran computer scientist with more than 30 years of knowledge, Vijay Vazirani is a professor for the School of Computer Science in the College of Computing at the Georgia Institute of Technology. His research has centered around the design of algorithms together with work on computational complexity theory, cryptography, and algorithmic game theory. He received his bachelor's from the Massachusetts Institute of Technology and his doctorate from the University of California, Berkeley. Previously, he was a professor of computer science at the Indian Institute of Technology, Delhi; a McKay Visiting Professor at the University of California, Berkeley; and a Distinguished Visitor at the Social and Information Sciences Laboratory at the California Institute of Technology.

During the 1980s, he made seminal contributions to the classical maximum matching problem, and key contributions to computational complexity theory. In 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 understanding the computability of market equilibria.  Two of his most significant research contributions were proving that if UNIQUE-SAT is in P, then NP = RP (Valiant–Vazirani theorem), and obtaining in 1980, along with Silvio Micali, an algorithm for maximum matchings in general graphs. The latter is still the most efficient known algorithm for the problem.  He is a Fellow of the Association for Computing Machinery, and in 2011, was honored with a Guggenheim Fellowship