Umesh Vazirani

Larger Photo

Professor

Contact Information

671 Soda Hall

tel: 510-642-0572

vazirani@cs.berkeley.edu

Links

Personal Homepage

Publications

Dissertations

Research Support

Derek Johnson
derekj@berkeley.edu

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

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)

Teaching Schedule

EECS C191A. Introduction to Quantum Computing I, TuTh 14:00-15:29, Soda 306

CS 170. Efficient Algorithms and Intractable Problems, TuTh 15:30-16:59, Stanley 105

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.

ACM SIGECOM Test of Time Award, 2024
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

Umesh Vazirani: Faculty Home Page