View source for Vijay Vazirani

{{Short description|Indian American professor of computer science (born 1957)}}
{{Infobox scientist
| name              = Vijay Vazirani
| image             = File:Vijay Vazirani UCI 2021.jpg
| image_size        = 200px
| caption           = At [[University of California, Irvine|UC Irvine]], 2021
| birth_date        = 1957
| birth_place       = [[India]]
| death_date        = 
| death_place       = 
| nationality       = [[United States|American]]
| fields            = [[algorithms]], [[computational complexity theory]], [[algorithmic game theory]].
| workplaces        = {{plainlist|1=
*[[Georgia Institute of Technology]]
*[[Indian Institute of Technology, Delhi]]
*[[University of California, Irvine]]
}}
| alma_mater        = [[MIT]] (Bachelor's degree)<br>[[University of California, Berkeley]] (PhD)<br>[[Harvard University]] (PostDoc)
| thesis_title      = Maximum Matchings without Blossoms
| thesis_year       = 1985
| doctoral_advisor  = [[Manuel Blum]]
| doctoral_students = {{plainlist|1=
*[[Naveen Garg]]
*[[Samir Khuller]]
}}
| known_for         = [[Valiant–Vazirani theorem]], [[Isolation lemma]]
| website           = {{URL|https://www.ics.uci.edu/~vazirani}}
| relatives         = [[Umesh Vazirani]] (brother)
| footnotes         = 
| prizes            = {{plainlist|1=
*[[ACM Fellow]]
*[[Guggenheim Fellowship]]
*[[John von Neumann Theory Prize]]
}}
}}

'''Vijay Virkumar Vazirani''' ({{langx|hi|विजय वीरकुमार वज़ीरानी}}; b. 1957<ref>[http://d-nb.info/gnd/122932196 ''Deutsche Nationalbibliothek'']</ref>) 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 first majored in electrical engineering at [[IIT Delhi|Indian Institute of Technology, Delhi]]  but in his second year he transferred to MIT and received his [[bachelor's degree]] in computer science 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]].<ref>{{mathgenealogy|id=78255}}</ref>
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 IIT 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,<ref>Three of his papers on the subject from that time period have over 100 citations each, according to Google scholar: {{citation | last1 = Micali | first1 = S. | author1-link = Silvio Micali | last2 = Vazirani | first2 = V. V. | contribution = An <math>\scriptstyle O(\sqrt{|V|}\cdot|E|)</math> algorithm for finding maximum matching in general graphs | doi = 10.1109/SFCS.1980.12 | pages = 17–27 | title = [[Symposium on Foundations of Computer Science|Proc. 21st IEEE Symp. Foundations of Computer Science]] | year = 1980| s2cid = 27467816 }}; {{citation|title=Matching is as easy as matrix inversion|first1=Ketan|last1=Mulmuley|authorlink=Ketan Mulmuley|first2=Umesh V.|last2=Vazirani|authorlink2=Umesh Vazirani|first3=Vijay V.|last3=Vazirani|journal=Combinatorica|volume=7|issue=1|year=1987|pages=105–113|doi=10.1007/BF02579206|s2cid=47370049}}; {{citation|first1=Richard M.|last1=Karp|author1-link=Richard M. Karp|first2=Umesh V.|last2=Vazirani|first3=Vijay V.|last3=Vazirani|contribution=An optimal algorithm for on-line bipartite matching|title=[[Symposium on Theory of Computing|Proc 22nd ACM Symp. Theory of Computing]]|year=1990|pages=352–358|doi=10.1145/100216.100262|isbn=0-89791-361-2|s2cid=822904}}.</ref> 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.<ref>{{citation|last1=Jerrum|first1=Mark R.|last2=Valiant|first2=Leslie G.|last3=Vazirani|first3=Vijay V.|doi=10.1016/0304-3975(86)90174-X|issue=2–3|journal=Theoretical Computer Science|mr=855970|pages=169–188|title=Random generation of combinatorial structures from a uniform distribution|volume=43|year=1986|doi-access=free}}. See {{citation|last=Bubley|first=Russ|doi=10.1007/978-1-4471-0695-1|isbn=1-85233-325-1|mr=1986183|page=120|publisher=Springer-Verlag|series=CPHC/BCS Distinguished Dissertations|title=Randomized algorithms: approximation, generation, and counting|url=https://books.google.com/books?id=in_lBwAAQBAJ&pg=PA120|year=2001|s2cid=266744010 }}; {{citation|last=Goldreich|first=Oded|isbn=9781139472746|page=229|publisher=Cambridge University Press|title=Computational Complexity: A Conceptual Perspective|url=https://books.google.com/books?id=EuguvA-w5OEC&pg=PA229|year=2008}}.</ref> 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<ref>{{citation|last1=Jain|first1=Kamal|last2=Vazirani|first2=Vijay V.|doi=10.1145/375827.375845|issue=2|journal=Journal of the ACM|mr=1868717|pages=274–296|title=Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation|volume=48|year=2001|s2cid=2353092}}. See {{citation|last1=Williamson|first1=David P.|last2=Shmoys|first2=David B.|isbn=9781139498173|page=191|publisher=Cambridge University Press|title=The Design of Approximation Algorithms|url=https://books.google.com/books?id=Cc_Fdqf3bBgC&pg=PA191|year=2011}}</ref> 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.

His research results also include proving, along with [[Leslie Valiant]], that if [[Boolean satisfiability problem#Extensions of SAT|UNIQUE-SAT]] is in [[P (complexity)|P]], then [[NP (complexity)|NP]] = [[RP (complexity)|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.
With Mehta, Saberi, and Umesh Vazirani, he showed in 2007 how to formulate the problem of choosing advertisements for [[AdWords]] as an [[online algorithm|online]] matching problem, and found a solution to this problem with optimal [[competitive ratio]].<ref>{{citation
 | last1 = Mehta | first1 = Aranyak
 | last2 = Saberi | first2 = Amin
 | last3 = Vazirani | first3 = Umesh
 | last4 = Vazirani | first4 = Vijay
 | doi = 10.1145/1284320.1284321
 | issue = 5
 | journal = Journal of the ACM
 | mr = 2359264
 | page = Art. 22, 19
 | title = AdWords and generalized online matching
 | volume = 54
 | year = 2007| s2cid = 8481313
 }}</ref>

==Awards and honors==
In 2005 both Vazirani and his brother [[Umesh Vazirani]] (also a theoretical computer scientist, at the [[University of California, Berkeley]]) were inducted as Fellows of the [[Association for Computing Machinery]].<ref>[http://fellows.acm.org/fellow_citation.cfm?id=UK41587&srt=all ACM Fellows Award: Umesh Vazirani] {{webarchive |url=https://web.archive.org/web/20071214200550/http://fellows.acm.org/fellow_citation.cfm?id=UK41587&srt=all |date=December 14, 2007 }}.</ref><ref>[http://fellows.acm.org/fellow_citation.cfm?id=UK17331&srt=all ACM Fellows Award: Vijay Vazirani] {{webarchive |url=https://web.archive.org/web/20071214193006/http://fellows.acm.org/fellow_citation.cfm?id=UK17331&srt=all |date=December 14, 2007 }}.</ref>
In 2011, he was awarded a [[Guggenheim Fellowship]].

In 2022, Vazirani received the [[John von Neumann Theory Prize]] for "fundamental and sustained contributions to the design of algorithms, including approximation algorithms, computational complexity theory, and algorithmic game theory, central to operations research and the management sciences".<ref>{{Cite web |title=2022 INFORMS Annual Meeting Awards Hall |url=https://meetings.informs.org/wordpress/indianapolis2022/awards-hall/ |access-date=2022-11-08 |website=2022 INFORMS Annual Meeting |date=5 October 2022 |language=en-US}}</ref>

==See also==
*[[List of Indian mathematicians]]

== References ==
<references/>

==External links==
*[https://www.ics.uci.edu/~vazirani/ Home page] at UC Irvine
*{{Google Scholar id|8eB7Q1kAAAAJ}}

{{John von Neumann Theory Prize recipients}}
{{Authority control}}

{{DEFAULTSORT:Vazirani, Vijay}}
[[Category:1951 births]]
[[Category:Living people]]
[[Category:Massachusetts Institute of Technology alumni]]
[[Category:University of California, Berkeley alumni]]
[[Category:Cornell University faculty]]
[[Category:Georgia Tech faculty]]
[[Category:University of California, Irvine faculty]]
[[Category:2005 fellows of the Association for Computing Machinery]]
[[Category:Theoretical computer scientists]]
[[Category:20th-century Indian mathematicians]]
[[Category:20th-century American mathematicians]]
[[Category:Indian emigrants to the United States]]
[[Category:American Hindus]]
[[Category:American people of Sindhi descent]]
[[Category:Indian Sindhi people]]
[[Category:American academics of Indian descent]]