# Umesh Vazirani

### Research Areas

- Theory (THY), Quantum computing, algorithms and complexity theory
- Security (SEC)

### Research Centers

- Berkeley Quantum Information and Computation Center (BQIC)
- Simons Institute for the Theory of Computing (SITC)

## Biography

Umesh Vazirani is the Roger A. Strauch Professor of EECS and the co-director of the Berkeley Quantum Computation Center (BQIC). His research interests lie primarily in quantum computing.

## Education

- 1986, Ph.D., Computer Science, UC Berkeley
- 1981, B.S., MIT

## Selected Publications

- S. Arora, S. Rao, and U. Vazirani, "Geometry, flows, and graph-partitioning algorithms," Communications ACM, vol. 51, no. 10, pp. 96-105, Oct. 2008.
- 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. Mehta, A. Saberi, U. Vazirani, and V. Vazirani, "Adwords and generalized online matching," J. ACM, vol. 54, no. 5, pp. Art. 22, Oct. 2007.
- S. Dasgupta, C. H. Papadimitriou, and U. Vazirani, Algorithms, Boston, MA: McGraw-Hill Higher Education, 2006.
- 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.
- 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.
- P. L. Vora, V. E. Knapp, and U. V. Vazirani, "Probabilistic privacy protection," U.S. Patent 6,470,299. Oct. 2002.
- 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.
- 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. J. Kearns and U. Vazirani, An Introduction to Computational Learning Theory, Cambridge, MA: MIT Press, 1994.
- 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.
- 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.
- 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.

## Awards, Memberships and Fellowships

- Symposium on Theory of Computing (STOC) Test of Time Award, 2023
- National Academy of Sciences (NAS) Member, 2018
- Delbert Ray Fulkerson Prize, 2012
- Association for Computing Machinery (ACM) Fellow, 2005
- NSF Presidential Young Investigator (PYI), 1987