# Faculty Publications - Umesh Vazirani

## Books

- S. Dasgupta, C. H. Papadimitriou, and U. Vazirani,
*Algorithms*, Boston, MA: McGraw-Hill Higher Education, 2006. [abstract] - M. J. Kearns and U. Vazirani,
*An Introduction to Computational Learning Theory*, Cambridge, MA: MIT Press, 1994. [abstract]

## Articles in journals or magazines

- S. Arora, S. Rao, and U. Vazirani, "Geometry, flows, and graph-partitioning algorithms,"
*Communications ACM*, vol. 51, no. 10, pp. 96-105, Oct. 2008. - A. Mehta, A. Saberi, U. Vazirani, and V. Vazirani, "Adwords and generalized online matching,"
*J. ACM*, vol. 54, no. 5, pp. Art. 22, Oct. 2007. - J. Vala, A. V. Thapliyal, S. Myrgren, U. Vazirani, D. S. Weiss, and K. B. Whaley, "Perfect pattern formation of neutral atoms in an addressable optical lattice,"
*Physical Review A (Atomic, Molecular, and Optical Physics)*, vol. 71, no. 3, pp. 32324-1-13, March 2005. - M. Grigni, L. J. Schulman, M. Vazirani, and U. Vazirani, "Quantum mechanical algorithms for the nonabelian hidden subgroup problem,"
*Combinatorica*, vol. 24, no. 1, pp. 137-154, Jan. 2004. - U. Vazirani, "On the power of quantum computation,"
*Physical Transactionsof the Royal Society A: Mathematical, Physical and Engineering Sciences*, vol. 356, no. 1743, pp. 1759-1768, Aug. 1998. - S. Khanna, R. Motwani, M. Sudan, and U. Vazirani, "On syntactic versus computational views of approximability,"
*SIAM J. on Computing*, vol. 28, no. 1, pp. 164-191, Feb. 1998. - E. Bernstein and U. Vazirani, "Quantum complexity theory,"
*SIAM J. on Computing*, vol. 26, no. 5, pp. 1411-1473, Oct. 1997. - C. H. Bennett, E. Bernstein, G. Brassard, and U. Vazirani, "Strengths and weaknesses of quantum computing,"
*SIAM J. on Computing*, vol. 26, no. 5, pp. 1510-1523, Oct. 1997. - M. Santha and U. Vazirani, "Generating quasi-random sequences from semi-random sources,"
*J. Computer and System Sciences*, vol. 33, no. 1, pp. 75-87, Aug. 1986.

## Articles in conference proceedings

- L. Orecchia, L. J. Schulman, U. Vazirani, and N. K. Vishnoi, "On partitioning graphs via single commodity flows," in
*Proc. 40th Annual ACM Symp. on Theory of Computing (STOC 2008)*, New York, NY: The Association for Computing Machinery, Inc., 2008, pp. 461-470. - A. M. Childs, L. J. Schulman, and U. Vazirani, "Quantum algorithms for hidden nonlinear structures," in
*Proc. 48th Annual IEEE Symp. on Foundations of Computer Science (FOCS 2007)*, Los Alamitos, CA: IEEE Computer Society, 2007, pp. 395-404. - U. Vazirani, "Quantum Physics and the Nature of Computation (Keynote Speech)," in
*Proc. 21st IEEE Intl. Parallel and Distributed Processing Symp. (IPDPS 2007)*, Piscataway, NJ: IEEE Press, 2007, pp. 15-16. - R. Khandekar, S. Rao, and U. Vazirani, "Graph partitioning using single commodity flows," in
*Proc. 38th Annual ACM Symp. on Theory of Computing*, New York, NY: ACM Press, 2006, pp. 385-390. - A. Mehta, A. Saberin, U. Vazirani, and V. Vazirani, "AdWords and generalized on-line matching," in
*Proc. 46th Annual IEEE Symp. on Foundations of Computer Science*, Los Alamitos, CA: IEEE Computer Society Press, 2005, pp. 264-273. - S. Arora, S. Rao, and U. Vazirani, "Expander flows, geometric embeddings and graph partitioning," in
*Proc. 36th Annual ACM Symp. on Theory of Computing*, New York, NY: ACM Press, 2004, pp. 222-231. - W. van Dam, M. Mosca, and U. Vazirani, "How powerful is adiabatic quantum computation?," in
*Proc. 42nd IEEE Symp. on Foundations of Computer Science*, Los Alamitos, CA: IEEE Computer Society Press, 2001, pp. 279-287. - R. M. Karp, U. Vazirani, and V. V. Vazirani, "An optimal algorithm for on-line bipartite matching," in
*Proc. 22nd Annual ACM Symp. on Theory of Computing*, H. Ortiz, Ed., New York, NY: ACM Press, 1990, pp. 352-358. - K. Mulmuley, U. Vazirani, and V. V. Vazirani, "Matching is as easy as matrix inversion," in
*Proc. 19th Annual ACM Conf. on Theory of Computing*, A. V. Aho, Ed., New York, NY: ACM Press, 1987, pp. 345-354. - U. Vazirani and V. V. Vazirani, "Random polynomial time is equal to slightly-random polynomial time," in
*Proc. 26th Annual IEEE Symp. on Foundations of Computer Science*, Washington, DC: IEEE Computer Society Press, 1985, pp. 417-428.

## Technical Reports

- R. Ostrovsky, S. Rajagopalan, and U. Vazirani, "Simple and Efficient Leader Election in the Full Information Model," EECS Department, University of California, Berkeley, Tech. Rep. UCB/CSD-94-800, March 1994. [abstract]
- R. M. Karp, U. Vazirani, and V. Vazirani, "An Optimal Algorithm for On-Line Bipartite Matching," EECS Department, University of California, Berkeley, Tech. Rep. UCB/ERL M91/18, 1991.

## Patents

- P. L. Vora, V. E. Knapp, and U. V. Vazirani, "Probabilistic privacy protection," U.S. Patent 6,470,299. Oct. 2002.

## Ph.D. Theses

- M. Drezgich, "On Quantum Search, Experts and Geometry," S. S. Sastry and U. Vazirani, Eds., EECS Department, University of California, Berkeley, Tech. Rep. UCB/EECS-2013-186, Dec. 2013. [abstract]

## Miscellaneous

- C. Moore, A. Russell, and U. Vazirani, "A Classical One-Way Function to Confound Quantum Adversaries," Jan. 2007.