Vijay V. Vazirani

# Vijay V. Vazirani

Professor
College of Computing
Georgia Institute of Technology

Ph.D., University of California, Berkeley, 1983
S.B., Massachusetts Institute of Technology, 1979

### Research Interests

Algorithmic problems in mathematical economics and game theory, design of efficient exact and approximation algorithms, computational complexity theory.

College of Computing,
KACB, Room 2142
266 Ferst Drive
Georgia Institute of Technology
Atlanta, Georgia 30332-0765
Phone: 404-894-5850
vazirani AT cc DOT gatech DOT edu

# Selected Papers by Topic

## Algorithmic Matching Theory

1. An $O(\sqrt{V}E)$ Algorithm for Finding Maximum Matching in General Graphs'', with S. Micali, Proc. 21st Annual IEEE Symposium on Foundations of Computer Science, (1980).
2. Maximum Matchings in General Graphs through Randomization'', with M. O. Rabin, Journal of Algorithms, Vol. 10, No. 4 (1989) 557-567.
3. Matching is as Easy as Matrix Inversion'', wtih K. Mulmuley and U. V. Vazirani, Combinatorica 7:1 (1987) 105-114.
4. Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs'', with M. Yannakakis, Discrete and Applied Mathematics, 25. (1989) 179-190.
5. A Theory of Alternating Paths and Blossoms for Proving Correctness of the $O(\sqrt{V} E)$ Maximum Matching Algorithm'', Combinatorica 14:1 (1994) 71-109.
6. An Optimal Algorithm for On-line Bipartite Matching'', with R. M. Karp and U.V. Vazirani, In Proc. 22nd Annual ACM Symposium on Theory of Computing (1990) 352-358.
7. Improved Simulated Annealing Algoirthm for the Permanent and Combinatorial Counting Problems'', with I. Bezakova, D. Stefankovic and E. Vigoda, SIAM Journal of Computing, 37(5) (2008) 1429 -1454.
8. A Proof of the MV Matching Algorithm'', in arXiv, 2014.

## Complexity Theory

1. NP is as Easy as Detecting Unique Solutions'', with L.G. Valiant, Theoretical Computer Science, 47(1986), 85-94.
2. Random Generation of Combinatorial Structures from a Uniform Distribution'', with M.R. Jerrum and L.G. Valiant, Theoretical Computer Science 44 (1986) 169-188.
3. Random Polynomial Time is Equal to Semi-random Polynomial Time'', with U.V. Vazirani, Proc. 26th Annual IEEE Symposium on Foundations of Computer Science (1985), 417-428.
4. A Computationally Motivated Definition of Parametric Estimation and its Applications to the Gaussian Distribution'', with L.J. Schulman, Combinatorica 25(4) (2005) 465-486.

## Approximation Algorithms

1. Finding k-cuts within Twice the Optimal'', with H. Saran, SIAM J. of Computing 24, 1 (1995).
2. A Primal-Dual Approximation Algorithm for the Generalized Steiner Network Problem'', with D. Williamson, M. Goemans and M. Mihail, Combinatorica, 15 (1995) 435-454.
3.  Approximate Max-flow Min-(multi)cut Theorems and their Applications'', with N. Garg and M. Yannakakis, SIAM J. of Computing 25, 2 (1996) 235-251.
4. Primal-Dual Approximation Algorithms for Integral Flow and Multicut in Trees, with Applications to Matching and Set Cover'', with N. Garg and M. Yannakakis, Algorithmica, 18 (1997) 3-20.
5.  Primal-Dual RNC Approximation Algorithms for (multi)Set (multi)Cover and Covering Integer Programs'', with S. Rajagopalan, SIAM J. of Computing 28, 2 (1998) 525-540.
6. Finding Separator Cuts in Planar Graphs within Twice the Optimal'', with N. Garg and H. Saran, SIAM J. of Computing 29, 1 (1999) 159-179.
7. Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation'', with K. Jain, Journal of ACM, Vol. 48 (2001) 274-296.
8. Greedy Facility Location Algorithms Analyzed using Dual Fitting with Factor-Revealing LP'', with K. Jain, M. Mahdian, E. Markakis, and A. Saberi, Journal of ACM, 50(6) (2003), 795-824.
9. New Geometry-Inspired Relaxations and Algorithms for the Metric Steiner Tree Problem'', with D. Chakrabarty and N. Devanur, Math Programming, Series A (2009).

## New Markets on the Internet

1. Adwords and Generalized Online Matching'', with A. Mehta, A. Saberi and U.V. Vazirani, Journal of ACM 54(5), 2007.
SIAM News article describing the work.
2. Equilibrium Pricing of Semantically Substitutable Digital Goods'', with K. Jain, in arXiv, (2012).
3. A Market for Scheduling, with Applications to Cloud Computing'', with N. Devanur, J. Garg, R. Mehta and S. Yazdanbod, in arXiv (2015).

## Computability of Market Equilibria

Polynomial Time Algorithms

1. Market Equilibrium via a Primal-Dual Algorithm for a Convex Program'', with N. Devanur, C.H. Papadimitriou, and A. Saberi, Journal of ACM, vol. 55(5) (2008).
2. The Spending Constraint Model for Market Equilibrium: Algorithmic, Existence and Uniqueness Results'', with N. Devanur, STOC 2004.
3. Market Equilibria for Homothetic, Quasi-Concave Utilities and Economies of Scale in Procudtion'', with K. Jain and Y. Ye, SODA (2005).
4. Eisenberg-Gale Markets: Algorithms and Game-Theoretic Properties'', with K. Jain, Games and Economic Behavior, 70(1), 2010.
5. Spending Constriant Utilities, with Applications to the Adwords Market'', Math of Operations Research 35(2), 2010.
6. A Perfect Price Discrimination Market Model with Production, and a Rational Convex Program for it'', with G. Goal, Math of Operations Research, 36: 762-782 (2011).
7. Complementary Pivot Algorithms

8. A Complementary Pivot Algorithm for Markets Under Separable, Piecewise-Linear Concave Utilities'', with J. Garg, R. Mehta and M. Sohoni, SIAM J. Comput. 44, 6 (2015).
9. On Computability of Equilibria in Markets with Production'', with J. Garg, SODA (2014).
10. Dichotomies in Equilibrium Computation, and Complementary Pivot Algorithms for a New Class of Non-Separable Utility Functions'', with J. Garg and R. Mehta, STOC (2014).
11. Complexity Results

12. Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities'', with M. Yannakakis, Journal of ACM, vol. 58(3) (2011).
13. Leontief Markets Can Solve Multivariate Polynomial Equations, Yielding FIXP and ETR Hardness'', with J. Garg, R. Mehta and S. Yazdanbod, In archive (2015).

## Algorithmic Game Theory

Nash Equilibrium

1. Settling Some Open Problems on 2-Player Symmetric Nash Equilibria'', with R. Mehta and S. Yazdanbod, SAGT (2015).
2. ETR-Completeness for Decision Versions of Multi-Player (Symmetric) Nash Equilibria'', with J. Garg, R. Mehta and S. Yazdanbod, ICALP (2015).
3. Nash Bargaining

4. The Notion of a Rational Convex Program, and an Algorithm for the Arrow-Debreu Nash Bargaining Game'', Journal of ACM, vol. 59(2) (2012).
5. Rational Convex Programs and Efficient Algorithms for 2-Player Nash and Nonsymmetric Bargaining Games'', SIAM J. Discrete Math, 26(3) (2012).
6. Submodularity Helps in Nash and Nonsymmetric Bargaining'', with D. Chakrabarty, G. Goel, L. Wang and C. Yu, SIAM J. Discrete Math, 28-1 (2014).
7. Cost-Sharing Mechanisms

8. Applications of Approximation Algorithms to Cooperative Games'', with K. Jain, In Proc. 33rd Annual ACM Symposium on Theory of Computing, (2001), 364-372.
9. Equitable Cost Allocations via Primal-Dual-Type Algorithms'', with K. Jain, SIAM J. Computing, 38(1), (2008).
10. Posted Price Profit Maximization for Multicast by Approximating Fixed Points'', with A. Mehta and S. Shenker, In Proc. ACM Conference on Electronic Commerce, EC '03, (2003) 218-219.
11. Strategyproof Cost-Sharing Mechanisms for Set Cover and Facility Location Games'', with N. Devanur and M. Mihail, In Proc. ACM Conference on Electronic Commerce, EC '03, (2003) 108-114.

## Cryptography

1. Efficient and Secure Pseudo-random Number Generation'', with U.V. Vazirani, In Proc. 25th Annual IEEE Symposium on Foundations of Computer Science (1984) 458-464.
2. Trapdoor Pseudo-Random Number Generators, with Applications to Protocol Design'', with U.V. Vazirani, In Proc. 24th Annual IEEE Symposium on Foundations of Computer Science (1984) 23-30.
3. A Graph Theoretic Approach to Software Watermarking'', with R. Venkatesan and S. Sinha, 4th International Information Hiding Workshop, Pittsburgh (2001).

## Information Theory

1. An Efficient Algorithm for Constructing Minimal Trellises for Codes over Finite Abelian Groups''. with H. Saran, and B.S. Rajan, IEEE Transactions on Information Theory, special issue on Codes and Complexity, Vol. 42, No. 6 (1996) 144-153.
2. The Art of Trellis Decoding'' is Computationally Hard -- for Large Fields'', with K. Jain and I. Mandoiu, IEEE Transactions on Information Theory, Vol. 44, No. 3 (1998) 1211-1214.
3. On the Capacity of Multiple Unicast Sessions in Unidrected Networks'', with K. Jain, R. Yeung and G. Yuval, ISIT 2005.

## Networking

1. A stochastic process on the hypercube with applications to peer-to-peer networks'', with M. Adler, E. Halperin, and R. M. Karp, Proc. STOC 2003.
2. Fast Monitoring of Traffic Subpopulations '', with A. Ramachandran, S. Seetharaman and N. Feamster, Internet Measurement Conference, Vouliagmeni, Greece (2008).
3. MINT: A Market for INternet Transit'', with V. Valancius, N. Feamster and R. Johari, ACM CoNEXT, Madrid, Spain (2008).
4. How Many Tiers? Pricing in the Internet Transit Market'', with V. Valancius, S. Sundaresan, U. Hassan, N. Feamster and R. Johari , SIGCOMM (2011).

## Biology

1. Diversity in Times of Adversity: Probabilistic Strategies in Microbial Survival Games.'', with D. M. Wolf and A. P. Arkin, Journal of Theoretical Biology, vol. 234, 227-253 (2005).
2. A Microbial Modified Prisoner's Dilemma Game: How Frequency-Dependent Selection can Lead to Random Phase Variation'', with D. M. Wolf and A. P. Arkin, Journal of Theoretical Biology, vol. 234, 255-262 (2005).
3. The game of survival: Sexual evolution in dynamic environments'', with R. Mehta, I. Panageas, G. Piliouras and P. Tetali, in arXiv (2015).