Vijay Vazirani (born May 21, 1975) is an Indian‑American computer scientist specializing in theoretical computer science. He is a professor in the Department of Electrical Engineering and Computer Sciences at the University of California, Berkeley. His research focuses on algorithms, approximation algorithms, and algorithmic game theory, with notable contributions to market equilibria, combinatorial optimization, and matching theory.
Early life and education
Vazirani completed his Bachelor of Technology (B.Tech.) degree in Computer Science and Engineering at the Indian Institute of Technology Bombay in 1995. He earned his Ph.D. in Computer Science from the Massachusetts Institute of Technology (MIT) in 1998 under the supervision of David Karger.
Academic career
After completing his doctorate, Vazirani held postdoctoral positions before joining the faculty of UC Berkeley in 2002. He has been promoted to full professor and serves as a faculty member in both the Computer Science Division and the Electrical Engineering and Computer Sciences (EECS) department.
Research contributions
-
Approximation Algorithms: Vazirani’s work has produced several foundational approximation algorithms for NP‑hard problems. He is co‑author of the widely used textbook Approximation Algorithms (Springer, 2001), which synthesizes key techniques in the field.
-
Algorithmic Game Theory and Market Equilibria: He has made influential contributions to the computational study of market equilibria, including algorithms for computing approximate equilibria in Fisher and Arrow‑Debreu markets. His research bridges combinatorial optimization with economic theory.
-
Matching Theory: Vazirani has investigated algorithms for stable and optimal matchings in various settings, extending classical results such as the Gale‑Shapley algorithm to more complex market models.
-
Complexity Theory: His early work addressed the complexity of approximation and hardness of approximation for several combinatorial problems.
Honors and awards
- ACM Fellow (2020) – Recognized for “contributions to the design of approximation algorithms and to algorithmic game theory.”
- Fulkerson Prize (2011) – Awarded jointly with co‑authors for work on approximation algorithms for graph partitioning problems.
- Best Paper Awards – Recipient of multiple best‑paper recognitions at conferences such as STOC, FOCS, and SODA.
Professional service
Vazirani has served on program committees for major conferences in theoretical computer science, including the Symposium on Theory of Computing (STOC) and the Foundations of Computer Science (FOCS). He has also acted as an associate editor for several journals, such as Journal of the ACM and SIAM Journal on Computing.
Personal life
Vijay Vazirani is the younger brother of Umesh Vazirani, a noted quantum computing researcher. Both brothers were born in India and later pursued academic careers in the United States.
Selected publications
- V. Vazirani, Approximation Algorithms, Springer, 2001.
- N. Fujishige, V. Vazirani, “An Approximation Algorithm for the Minimum-Cost Matching Problem,” SIAM Journal on Computing, 2005.
- R. Cole, V. Vazirani, “Market Equilibria in Polynomial Time,” Proceedings of STOC, 2009.
This entry reflects information available from reliable academic and institutional sources as of the last update.