Vijay Vazirani

Vijay Vazirani

Vijay Vazirani in 2010 visiting the University of California, Berkeley.
Born 1957
Nationality Indian American
Alma mater MIT (Bachelor's degree)
University of California, Berkeley (PhD)
Occupation Professor of Computer Science at Georgia Tech.
Notes
He is the brother of Umesh Vazirani

Vijay Virkumar Vazirani (Hindi: विजय वीरकुमार वज़ीरानी; b. 1957[1]) is an Indian American Professor of Computer Science at Georgia Tech.[2]

He received his Bachelor's degree from MIT in 1979 and his Ph.D. from the University of California, Berkeley in 1983. During the early to mid nineties, he was a Professor of Computer Science at the Indian Institute of Technology, Delhi. Vijay Vazirani 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.

Career

His 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,[3] and some 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.

Two of his most significant research results were proving, along with Leslie Valiant, that if UNIQUE-SAT is in P, then NP = RP (Valiant–Vazirani theorem), 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.

He is the brother of UC Berkeley computer science professor Umesh Vazirani. In 2005 they both were inducted as Fellows of the Association for Computing Machinery.[4][5] In 2011, he was awarded a Guggenheim Fellowship.

See also

References

  1. ↑ Deutsche Nationalbibliothek
  2. ↑ Faculty page at Georgia Tech
  3. ↑ Three of his papers on the subject from that time period have over 100 citations each, according to Google scholar: Micali, S.; Vazirani, V. V. (1980), "An algorithm for finding maximum matching in general graphs", Proc. 21st IEEE Symp. Foundations of Computer Science, pp. 17–27, doi:10.1109/SFCS.1980.12; Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V. (1987), "Matching is as easy as matrix inversion", Combinatorica, 7 (1): 105–113, doi:10.1007/BF02579206; Karp, Richard M.; Vazirani, Umesh V.; Vazirani, Vijay V. (1990), "An optimal algorithm for on-line bipartite matching", Proc 22nd ACM Symp. Theory of Computing, pp. 352–358, doi:10.1145/100216.100262, ISBN 0-89791-361-2.
  4. ↑ ACM Fellows Award: Umesh Vazirani Archived December 14, 2007, at the Wayback Machine..
  5. ↑ ACM Fellows Award: Vijay Vazirani Archived December 14, 2007, at the Wayback Machine..
This article is issued from Wikipedia - version of the 11/18/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.