# Umesh Vazirani

#2,151

Most Influential Person Now

Indian theoretical computer scientist

## Umesh Vazirani's AcademicInfluence.com Rankings

Umesh Vaziranicomputer-science Degrees

Computer Science

#166

World Rank

#173

Historical Rank

#99

USA Rank

Database

#196

World Rank

#203

Historical Rank

#98

USA Rank

## Download Badge

Computer Science

## Umesh Vazirani's Degrees

- PhD Computer Science University of California, Berkeley

## Similar Degrees You Can Earn

## Why Is Umesh Vazirani Influential?

(Suggest an Edit or Addition)According to Wikipedia, Umesh Virkumar Vazirani is an Indian–American academic who is the Roger A. Strauch Professor of Electrical Engineering and Computer Science at the University of California, Berkeley, and the director of the Berkeley Quantum Computation Center. His research interests lie primarily in quantum computing. He is also a co-author of a textbook on algorithms.

## Umesh Vazirani's Published Works

### Published Works

- An Introduction to Computational Learning Theory (1994) (1878)
- Quantum complexity theory (1993) (1851)
- Strengths and Weaknesses of Quantum Computing (1997) (1298)
- AdWords and generalized on-line matching (2005) (808)
- Matching is as easy as matrix inversion (1987) (770)
- An optimal algorithm for on-line bipartite matching (1990) (746)
- Quantum walks on graphs (2000) (666)
- Expander flows, geometric embeddings and graph partitioning (2004) (622)
- Classical command of quantum systems (2013) (331)
- On syntactic versus computational views of approximability (1994) (304)
- How powerful is adiabatic quantum computation? (2001) (285)
- Generating Quasi-random Sequences from Semi-random Sources (1986) (270)
- Expander flows, geometric embeddings and graph partitioning (2009) (251)
- Fully device-independent quantum key distribution. (2012) (219)
- Fully device independent quantum key distribution (2013) (215)
- Dense quantum coding and quantum finite automata (2002) (209)
- On the complexity and verification of quantum random circuit sampling (2018) (184)
- Graph partitioning using single commodity flows (2006) (156)
- Quantum mechanical algorithms for the nonabelian hidden subgroup problem (2001) (144)
- Dense quantum coding and a lower bound for 1-way quantum automata (1998) (142)
- On Two Geometric Problems Related to the Traveling Salesman Problem (1984) (140)
- An area law and sub-exponential algorithm for 1D systems (2013) (140)
- Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract) (1984) (137)
- How "Quantum" is the D-Wave Machine? (2014) (131)
- Quantum Algorithms (2001) (130)
- Quantum bit escrow (2000) (122)
- "Go with the winners" algorithms (1994) (118)
- A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games (2012) (107)
- The quantum communication complexity of sampling (1998) (107)
- Random polynomial time is equal to slightly-random polynomial time (1985) (102)
- Efficient and Secure Pseudo-Random Number Generation (1984) (101)
- Algorithms, games, and evolution (2014) (100)
- A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians (2015) (96)
- Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources (1987) (95)
- Molecular scale heat engines and scalable quantum computation (1999) (95)
- A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device (2018) (94)
- The detectability lemma and quantum gap amplification (2008) (94)
- Certifiable quantum dice: or, true random number generation secure against quantum adversaries (2012) (91)
- On partitioning graphs via single commodity flows (2008) (82)
- Quantum Algorithms for Hidden Nonlinear Structures (2007) (82)
- Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources (1985) (71)
- Certifiable quantum dice (2012) (71)
- Rigorous RG Algorithms and Area Laws for Low Energy Eigenstates in 1D (2016) (68)
- Improved one-dimensional area law for frustration-free systems (2011) (68)
- Efficiency considerations in using semi-random sources (1987) (66)
- Efficient and Secure Pseudo-Random Number Generation (Extended Abstract) (1984) (62)
- Quantum Supremacy and the Complexity of Random Circuit Sampling (2018) (60)
- NC Algorithms for Comparability Graphs, Interval Gaphs, and Testing for Unique Perfect Matching (1985) (60)
- Another way to approach zero entropy for a finite system of atoms (2004) (59)
- Scalable NMR Quantum Computation (1998) (58)
- Polytopes, permanents and graphs with large factors (1988) (57)
- A mildly exponential approximation algorithm for the permanent (1992) (55)
- A Markovian extension of Valiant's learning model (1990) (54)
- Trapdoor pseudo-random number generators, with applications to protocol design (1983) (51)
- A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem (1993) (50)
- On the power of quantum computation (1998) (44)
- Graph products and chromatic numbers (1989) (43)
- Certifiable Quantum Dice - Or, testable exponential randomness expansion (2011) (42)
- Simple and efficient leader election in the full information model (1994) (42)
- Computing with highly mixed states (2000) (42)
- Geometry, flows, and graph-partitioning algorithms (2008) (41)
- Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality (2019) (40)
- Global Wire Routing in Two-Dimensional Arrays (Extended Abstract) (1983) (40)
- A polynomial-time algorithm for the ground state of 1D gapped local Hamiltonians (2013) (38)
- Random Polynomial Time is Equal to Semi-Random Polynomial Time (1988) (37)
- Is Quantum Mechanics Falsifiable? A computational perspective on the foundations of Quantum Mechanics (2012) (35)
- The detectability lemma and its applications to quantum Hamiltonian complexity (2011) (35)
- Simpler Proofs of Quantumness (2020) (34)
- Randomness, adversaries and computation (random polynomial time) (1986) (33)
- Simulating quadratic dynamical systems is PSPACE-complete (preliminary version) (1994) (33)
- Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem (2004) (31)
- Perfect pattern formation of neutral atoms in an addressable optical lattice (2005) (29)
- Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law (2014) (28)
- Multiplicative updates in coordination games and the theory of evolution (2012) (27)
- A natural encoding scheme proved probabilistic polynomial complete (1982) (26)
- A classical one-way function to confound quantum adversaries (2007) (20)
- Quantum algorithms and the fourier transform (2004) (19)
- Classically verifiable quantum advantage from a computational Bell test (2021) (19)
- Relativizing versus Nonrelativizing Techniques: The Role of Local Checkability (1992) (18)
- RSA bits are .732 + ε secure (1984) (18)
- Comment on "Distinguishing Classical and Quantum Models for the D-Wave Device" (2014) (17)
- Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States (2018) (17)
- Certifiable Randomness from a Single Quantum Device (2018) (17)
- The two-processor scheduling problem is in R-NC (1985) (16)
- Graph partitioning using single commodity flows (2009) (16)
- Learning probability distributions (2000) (16)
- Quantum Hamiltonian complexity and the detectability lemma (2010) (16)
- Lower bounds for quantum computation and communication (1999) (16)
- The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach (2011) (16)
- Classical command of quantum systems via rigidity of CHSH games (2012) (16)
- Robust device independent quantum key distribution (2014) (15)
- On the learnability of finite automata (1988) (15)
- The Two-Processor Scheduling Problem is in Random NC (1989) (12)
- Interactive Protocols for Classically-Verifiable Quantum Advantage (2021) (12)
- Efficiency Considerations in Using Semi-random Sources (Extended Abstract) (1987) (11)
- Computing with highly mixed states (extended abstract) (2000) (10)
- NC Algorithms for Comparability Graphs, Interval Graphs, and Unique Perfect Matchings (1986) (10)
- (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem (2020) (10)
- A polynomial-time classical algorithm for noisy random circuit sampling (2022) (9)
- Quantum encodings and applications to locally decodable codes and communication complexity (2004) (8)
- Reducibility Among Protocols (1983) (8)
- Rapidly mixing markov chains (1992) (8)
- The Duality Gap for Two-Team Zero-Sum Games (2019) (7)
- On the space efficiency of one way quantum finite automata (1998) (6)
- Sampling a Population with a Semi-Random Source (1986) (5)
- Computational Learning Theory (1995) (5)
- An efficient algorithm for finding the ground state of 1D gapped local hamiltonians (2014) (5)
- Fourier Transforms and Quantum Computation (2000) (5)
- Introduction to Special Section on Quantum Computation (1997) (4)
- Choosing a reliable hypothesis (1993) (4)
- Quantum fourier sampling, the hidden subgroup problem, and beyond (2000) (4)
- Efficient Certifiable Randomness from a Single Quantum Device (2022) (4)
- Performance of the rigorous renormalization group for first-order phase transitions and topological phases (2020) (3)
- RSA Bits are 732+epsilon Secure (1983) (2)
- The Probably Approximately Correct Learning Model (1994) (2)
- LIMITS ON QUANTUM ADIABATIC OPTIMIZATION WARNING : ROUGH MANUSCRIPT ! (2003) (2)
- Erratum: Fully Device-Independent Quantum Key Distribution [Phys. Rev. Lett. 113, 140501 (2014)]. (2016) (2)
- The Vapnik-Chervonenkis Dimension (1994) (1)
- Quantum Physics and the Nature of Computation (2005) (1)
- Quantum Pseudoentanglement (2022) (1)
- Go-With-The-Winners Heuristic (1999) (1)
- Perfect initialization of a quantum computer of neutral atoms in an optical lattice of large lattice constant (2003) (1)
- Communication costs in the performance of unrelated tasks: Continuum models and finite models (1991) (1)
- Keynote Speech: Quantum Physics and the Nature of Computation (2007) (1)
- Deniable encryption in a Quantum world (2021) (1)
- Quantum Computation and Information (1998) (1)
- Scalability, Complexity and Reliability in Quantum Information Processing (2007) (0)
- Dynamic Programming 6.1 Shortest Paths in Dags, Revisited (0)
- Weak and Strong Learning (1994) (0)
- Today's Topics: Lower Bounds for Constant Depth Circuits Razborovvsmolensky a Learning Algorithm for Constant Depth Circuits Hastad Has866 and Liniallmansourrnisan Lmn899 4.1 Lower Bounds for Constant Depth Circuits (1999) (0)
- Grover's Search Algorithm and Quantum Lower Bounds (2000) (0)
- Center for Quantum Algorithms and Complexity (2014) (0)
- Randomized Algorithms (Dagstuhl Seminar 9124) (2021) (0)
- Learning Finite Automata by Experimentation (1994) (0)
- " Center for Quantum Algorithms and Complexity " Report Title (2014) (0)
- A Classical Leash for a Quantum Tiger: Key Distribution with Miminmal Assumptions (2015) (0)
- Learning Natural Language : A review of formal and computational approachesNancy (2007) (0)
- Quantum State Description Complexity (Invited Talk) (2011) (0)
- Learning in the Presence of Noise (1994) (0)
- Rigorous renormalization group at first-order phase transitions (2018) (0)
- Annotated Bibliography of Selected Publications (2005) (0)
- Quantum State Description Complexity (2011) (0)
- An Optimal Algorithm for On-lineBipartite Matching (2015) (0)
- A Quantum Algorithm for the Ferromagnetic Ising Model (Manuscript in preparation) (2008) (0)
- An efficiently-verifiable test of quantum advantage (2020) (0)
- Rigorous RG Algorithms and Area Laws for Low Energy Eigenstates in 1D (2017) (0)
- Reducibility in PAC Learning (1994) (0)
- OCCAM'S RAZOR (1975) (0)
- Global Wire Routing in Two-Dimensional Arrays 1 (1987) (0)
- Parallel searching of multidimensional cubes (1993) (0)
- A polynomial-time algorithm for the ground state of 1 D gapped local Hamiltonians Supplementary material (2015) (0)
- A Final Assignment: (2019) (0)
- Decoding Ag-codes and Let W Be a Vector Having Acknowledgments Decoding Ag-codes (2007) (0)
- Quantum Information Processing (2004) (0)
- Appendix: Some Tools for Probabilistic Analysis (1994) (0)
- Algorithms, Games, and Evolution (Invited Talk) (2014) (0)
- Philosophical Transactions of the Royal Society of London. Series A: Mathematical, Physical and Engineering Sciences: 356 (1743) (1998) (0)
- DP Solution Guidelines (2020) (0)
- Quantum computing and quantum complexity theory (2000) (0)
- On the complexity and verification of quantum random circuit sampling (2018) (0)
- The Quantum Algorithms -final Report (2012) (0)

This paper list is powered by the following services:

## Other Resources About Umesh Vazirani

## What Schools Are Affiliated With Umesh Vazirani?

Umesh Vazirani is affiliated with the following schools: