Vijay Vazirani

Source: Wikipedia, the free encyclopedia.
Vijay Vazirani
MIT (Bachelor's degree)
University of California, Berkeley (PhD)
Harvard University (PostDoc)
Known forValiant–Vazirani theorem, Isolation lemma
RelativesUmesh Vazirani (brother)
Awards
Scientific career
Fields
algorithms, computational complexity theory, algorithmic game theory
.
Institutions
Thesis Maximum Matchings without Blossoms  (1985)
Doctoral advisorManuel Blum
Doctoral students
Websitewww.ics.uci.edu/~vazirani

Vijay Virkumar Vazirani (

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

Ph.D. from the University of California, Berkeley in 1983. His dissertation, Maximum Matchings without Blossoms, was supervised by Manuel Blum.[2]
After postdoctoral research with
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

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 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. With Mehta, Saberi, and Umesh Vazirani, he showed in 2007 how to formulate the problem of choosing advertisements for

competitive ratio.[6]

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.[7][8] 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".[9]

See also

References

  1. ^ Deutsche Nationalbibliothek
  2. ^ Vijay Vazirani at the Mathematics Genealogy Project
  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",
    S2CID 822904
    .
  4. ISBN 9781139472746
    .
  5. ISBN 9781139498173
  6. S2CID 8481313
  7. ^ ACM Fellows Award: Umesh Vazirani Archived December 14, 2007, at the Wayback Machine.
  8. ^ ACM Fellows Award: Vijay Vazirani Archived December 14, 2007, at the Wayback Machine.
  9. ^ "2022 INFORMS Annual Meeting Awards Hall". 2022 INFORMS Annual Meeting. 5 October 2022. Retrieved 2022-11-08.

External links

Retrieved from "https://en.wikipedia.org/w/index.php?title=Vijay_Vazirani&oldid=1216871096"