Umesh Vazirani

Professor
Computer Science Division
671 Soda Hall
(510)642-0572
(510) 642-5775 (fax)
my_last_name AT cs DOT berkeley DOT edu

Contents: Selected Publications / Courses / Students

Selected Publications

Graph partitioning using single commodity flows. with R. Khandekar, S. Rao, Proceedings of Symposium on the Theory of Computing, 2006.
AdWords and the Generalized Bipartite Matching Problem. with A. Mehta, A. Saberi, V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 2005.
SIAM News Article by Sara Robinson pdf
Expander Flows, Geometric Embeddings and Graph Partitioning. with S. Arora, S. Rao, Proceedings of Symposium on the Theory of Computing, 2004.
Quantum Mechanical Algorithms for the Non-Abelian Hidden Subgroup Problem. with M. Grigni, L. Schulman, M. Vazirani, Proceedings of Symposium on the Theory of Computing, 2001; Combinatorica, Volume 24, Number 1, pp 137-154, January 2004.
Limits on Quantum Adiabatic Optimization. with W. van Dam, manuscript.
Dense Quantum Coding and Quantum Finite Automata. with A. Ambainis, A. Nayak, A. Ta-Shma, Proceedings of Symposium on the Theory of Computing, 1999; Journal of the ACM, Volume 49, Issue 4, 2002.
How Powerful is Adiabatic Quantum Computation. with W. van Dam, M. Mosca, Proceedings of Symposium on the Foundations of Computer Science, 2001.
Quantum Walks on Graphs. with D. Aharonov, A. Ambainis, J. Kempe, Proceedings of Symposium on the Theory of Computing, 1999.
Computing with Highly Mixed States. with A. Ambainis, L. Schulman, Proceedings of Symposium on the Theory of Computing, 2000. Journal of the ACM Volume 53, Issue 3 (May 2006), Pages: 507 - 531.
Quantum Bit Escrow. with D. Aharonov, A. Ta-Shma, A. Yao, Proceedings of Symposium on the Theory of Computing, 2000.
Molecular Scale Heat Engines and Scalable Quantum Computation. with L. Schulman, Proceedings of Symposium on the Theory of Computing, 1999.
The Quantum Communication Complexity of Sampling. with A. Ambainis, L. Schulman, A. Ta-Shma, A. Wigderson, Proceedings of Symposium on the Foundations of Computer Science, 1998. Siam J. Comput., Vol. 32, No. 6, pp. 1570-1585, 2003.
On the Power of Quantum Computation. Philosophical Transactions of the Royal Society London A (1998) 356, 1759-1768.
Go With the Winners Algorithms. with D. Aldous, Proceedings of Symposium on the Foundations of Computer Science, 1994.
On syntactic versus computational views of approximability. with S. Khanna, R. Motwani, M. Sudan, Proceedings of Symposium on the Foundations of Computer Science, 1994. SIAM Journal on Computing, 28(1): 164-191, February 1999.
Simple and Efficient Leader Election in the Full Information Model. with R. Ostrowsky, S. Rajagopalan, Proceedings of Symposium on the Theory of Computing, 1994.
Simulating Quadratic Dynamical Systems is PSPACE-hard. with S. Arora, Y. Rabani, Proceedings of Symposium on the Theory of Computing, 1994.
Quantum Complexity Theory. with E. Bernstein, Proceedings of Symposium on the Theory of Computing, 1993. Special issue on Quantum Computation of the Siam Journal of Computing, Oct. 1997.
Strengths and Weaknesses of Quantum Computation. with C. Bennett, E. Bernstein, G. Brassard, Special issue on Quantum Computation of the Siam Journal of Computing, Oct. 1997.
A Mildly Exponential Algorithm for Approximating the Permanent. with M. Jerrum, Proceedings of Symposium on the Foundations of Computer Science, 1992. invited paper, special issue of Algorithmica 16 (1996), 392-401.
Choosing a Reliable Hypothesis. with W. Evans, S. Rajagopalan, Proceedings of the Symposium on Computational Learning Theory}, 1993.
A Markovian Extension of Valiant's Learning Model. with D. Aldous, Proceedings of Symposium on the Foundations of Computer Science, 1990. Information and Computation, Vol. 117, No. 2, pp~181-186, 1995.
Relativizing versus Nonrelativizing Techniques: the Role of Local Checkability. with S. Arora, R. Impagliazzo; early draft.
An Optimal Online Bipartite Matching Algorithm. with R. Karp, V. Vazirani, Proceedings of Symposium on the Theory of Computing, 1990.
Matching is as Easy as Matrix Inversion. with K. Mulmuley, V. Vazirani, Proceedings of Symposium on the Theory of Computing, 1987. Combinatorica, Vol. 7, No. 1, 1987.
Efficiency Considerations in Using Semi-Random Sources. Proceedings of Symposium on the Theory of Computing, 1987.
Random Polynomial Time is Equal to Semi-Random Polynomial Time. with V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 1985.
Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Semi-Random Sources. Proceedings of Symposium on the Theory of Computing, 1985. Combinatorica, Vol. 7, No. 4, 1987.
Generating Quasi-Random Sequences from Semi-Random Sources. with M. Santha, Proceedings of Symposium on the Foundations of Computer Science, 1984, Journal Comput. Sys. Sci., Vol. 33, No. 1, 1986.
Efficient and Secure Pseudo-Random Number Generation. with V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 1984.
Trapdoor Pseudo-Random Number Generators, with Applications to Protocol Design. with V. Vazirani, Proceedings of Symposium on the Foundations of Computer Science, 1983.