Sotabase

Career

· Co-director, Berkeley Quantum Computation Center (BQIC), University of California, Berkeley2004–
· PhD in Computer Science, University of California, Berkeley1986–
· Roger A. Strauch Professor of EECS, University of California, Berkeley1986–
· Roger A. Strauch Professor of Electrical Engineering and Computer Science, University of California, Berkeley1986–
· B.S. in Computer Science, Massachusetts Institute of Technology1981–
· B.S., Computer Science, Massachusetts Institute of Technology (MIT)1976–1981
· Research Director for Quantum Computing, Simons Institute for the Theory of Computing, University of California, Berkeley

Publications (155)

Quantum complexity theory
Symposium on the Theory of Computing · 1993
2,220
cited
Strengths and Weaknesses of Quantum Computing
SIAM journal on computing (Print) · 1997
1,482
cited
AdWords and generalized on-line matching
IEEE Annual Symposium on Foundations of Computer Science · 2005
915
cited
An optimal algorithm for on-line bipartite matching
Symposium on the Theory of Computing · 1990
860
cited
Matching is as easy as matrix inversion
Symposium on the Theory of Computing · 1987
841
cited
Quantum walks on graphs
Symposium on the Theory of Computing · 2000
721
cited
Expander flows, geometric embeddings and graph partitioning
Symposium on the Theory of Computing · 2004
671
cited
Fully device independent quantum key distribution
Communications of the ACM · 2012
450
cited
Classical command of quantum systems
Nature · 2013
372
cited
On the complexity and verification of quantum random circuit sampling
Nature Physics · 2018
334
cited
On syntactic versus computational views of approximability
Proceedings 35th Annual Symposium on Foundations of Computer Science · 1994
319
cited
How powerful is adiabatic quantum computation?
Proceedings IEEE International Conference on Cluster Computing · 2001
317
cited
Generating Quasi-random Sequences from Semi-random Sources
Journal of computer and system sciences (Print) · 1986
286
cited
Dense quantum coding and quantum finite automata
JACM · 2002
248
cited
Quantum Algorithms
Latin American Symposium on Theoretical Informatics · 2001
198
cited
Graph partitioning using single commodity flows
Symposium on the Theory of Computing · 2006
180
cited
An area law and sub-exponential algorithm for 1D systems
2013
165
cited
Dense quantum coding and a lower bound for 1-way quantum automata
Symposium on the Theory of Computing · 1998
164
cited
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
IEEE Annual Symposium on Foundations of Computer Science · 2018
163
cited
Can you beat treewidth?
IEEE Annual Symposium on Foundations of Computer Science · 2007
156
cited
Sotabase
Umesh Vazirani | Researcher Profile | Sotabase | Sotabase