Approximation Algorithms

H. Saran and V.V. Vazirani,
Finding kcuts within Twice the Optimal.
SIAM J. of Computing 24, 1 (1995).

N. Garg, V.V. Vazirani, and M. Yannakakis,
Approximate Maxflow Min(multi)cut Theorems and their Applications.
SIAM J. of Computing 25, 2 (1996) 235251.

D. Williamson, M. Goemans, M. Mihail, and V.V. Vazirani,
A PrimalDual Approximation Algorithm for the Generalized
Steiner Network Problem.
Combinatorica, 15 (1995) 435454.

S. Rajagopalan and V.V. Vazirani,
PrimalDual RNC Approximation Algorithms for (multi)Set
(multi)Cover and Covering Integer Programs.
SIAM J. of Computing 28, 2 (1998) 525540.

N. Garg, H. Saran, and V.V. Vazirani,
Finding Separator Cuts in Planar Graphs within
Twice the Optimal.
SIAM J. of Computing 29, 1 (1999) 159179.
Coding Theory

V.V. Vazirani, H. Saran, and B.S. Rajan,
An Efficient Algorithm for Constructing Minimal Trellises for
Codes over Finite Abelian Groups.
IEEE Transactions on Information Theory, special issue on
Codes and Complexity, Vol. 42, No. 6 (1996) 144153.

K. Jain, I. Mandoiu, and V.V. Vazirani,
The ``Art of Trellis Decoding'' is Computationally
Hard  for Large Fields.
IEEE Transactions on Information Theory, Vol. 44, No. 3 (1998) 12111214.
Algorithmic Matching Theory

S. Micali and V.V. Vazirani,
An $O(\sqrt{V}E)$ Algorithm for Finding Maximum Matching in General Graphs.
Proc. 21st Annual IEEE Symposium on Foundations of Computer Science
(1980) 1727.

M.O. Rabin and V.V. Vazirani,
Maximum Matchings in General Graphs through Randomization.
Journal of Algorithms, Vol. 10, No. 4 (1989) 557567.

K. Mulmuley, U.V. Vazirani, and V.V. Vazirani,
Matching is as Easy as Matrix Inversion.
Combinatorica 7:1 (1987) 105114.

V.V. Vazirani and M. Yannakakis,
Pfaffian Orientations, 0/1 Permanents, and Even Cycles in Directed Graphs.
Discrete and Applied Mathematics, 25. (1989) 179190.

V.V. Vazirani,
A Theory of Alternating Paths and Blossoms for Proving Correctness of
the $O(\sqrt{V} E)$ Maximum Matching Algorithm.
Combinatorica 14:1 (1994) 71109.

H. Narayanan, H. Saran, and V.V. Vazirani,
Randomized Parallel Algorithms for Matroid Union and Intersection,
with Applications to Arboresences, and EdgeDisjoint Spanning Trees.
SIAM J. Computing Vol. 23 No. 2 (1994) 387397.
Complexity Theory

L.G. Valiant and V.V. Vazirani,
NP is as Easy as Detecting Unique Solutions.
Theoretical Computer Science, 47(1986), 8594.

M.R. Jerrum, L.G. Valiant, and V.V. Vazirani,
Random Generation of Combinatorial Structures from a Uniform Distribution.
Theoretical Computer Science 44 (1986) 169188.

U.V. Vazirani and V.V. Vazirani,
Random Polynomial Time is Equal to Semirandom Polynomial Time.
Proc. 26th Annual IEEE Symposium on Foundations of Computer Science
(1985), 417428.