Umesh V. Vazirani

Publication Activity (10 Years)

Years Active: 1982-2024
Publications (10 Years): 25

Top Venues

CoRR

ITCS

STOC

FOCS

Publications

Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou
Quantum Pseudoentanglement. ITCS (2024)
Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou
Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure. CCC (2024)
Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou
Public-key pseudoentanglement and the hardness of learning ground state entanglement structure. CoRR (2023)
Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh V. Vazirani
A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling. STOC (2023)
Andrea Coladangelo, Shafi Goldwasser, Umesh V. Vazirani
Deniable encryption in a Quantum world. STOC (2022)
Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Zixin Zhou
Quantum Pseudoentanglement. CoRR (2022)
Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick
Efficient Certifiable Randomness from a Single Quantum Device. CoRR (2022)
Andrea Coladangelo, Shafi Goldwasser, Umesh V. Vazirani
Deniable Encryption in a Quantum World. CoRR (2021)
Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. J. ACM 68 (5) (2021)
Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, Norman Y. Yao
Classically-Verifiable Quantum Advantage from a Computational Bell Test. CoRR (2021)
András Gilyén, Matthew B. Hastings, Umesh V. Vazirani
(Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. STOC (2021)
Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick
Simpler Proofs of Quantumness. TQC (2020)
András Gilyén, Umesh V. Vazirani
(Sub)Exponential advantage of adiabatic quantum computation with no sign problem. CoRR (2020)
Adam Bouland, Bill Fefferman, Umesh V. Vazirani
Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract). ITCS (2020)
Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick
Simpler Proofs of Quantumness. CoRR (2020)
Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani
"Quantum Supremacy" and the Complexity of Random Circuit Sampling. ITCS (2019)
Adam Bouland, Bill Fefferman, Umesh V. Vazirani
Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality. CoRR (2019)
Umesh V. Vazirani, Thomas Vidick
Fully device independent quantum key distribution. Commun. ACM 62 (4) (2019)
Leonard J. Schulman, Umesh V. Vazirani
The duality gap for two-team zero-sum games. Games Econ. Behav. 115 (2019)
Chinmay Nirkhe, Umesh V. Vazirani, Henry Yuen
Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States. ICALP (2018)
Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick
Certifiable Randomness from a Single Quantum Device. CoRR (2018)
Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. FOCS (2018)
Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani
Quantum Supremacy and the Complexity of Random Circuit Sampling. CoRR (2018)
Leonard J. Schulman, Umesh V. Vazirani
The Duality Gap for Two-Team Zero-Sum Games. ITCS (2017)
Itai Arad, Zeph Landau, Umesh V. Vazirani, Thomas Vidick
Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D. ITCS (2017)
Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani
Algorithms, games, and evolution. Proc. Natl. Acad. Sci. USA 111 (29) (2014)
Umesh V. Vazirani, Thomas Vidick
Robust device independent quantum key distribution. ITCS (2014)
Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani
Algorithms, Games, and Evolution (Invited Talk). FSTTCS (2014)
Zeph Landau, Umesh V. Vazirani, Thomas Vidick
An efficient algorithm for finding the ground state of 1D gapped local hamiltonians. ITCS (2014)
Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law. FOCS (2014)
Ben W. Reichardt, Falk Unger, Umesh V. Vazirani
Classical command of quantum systems. Nat. 496 (7446) (2013)
Ben W. Reichardt, Falk Unger, Umesh V. Vazirani
A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games. ITCS (2013)
Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani
Multiplicative updates in coordination games and the theory of evolution. ITCS (2013)
Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani
Multiplicative Updates in Coordination Games and the Theory of Evolution CoRR (2012)
Umesh V. Vazirani, Thomas Vidick
Certifiable quantum dice: or, true random number generation secure against quantum adversaries. STOC (2012)
Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani
The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach. FOCS (2011)
Umesh V. Vazirani
Quantum State Description Complexity (Invited Talk). FSTTCS (2011)
Rohit Khandekar, Satish Rao, Umesh V. Vazirani
Graph partitioning using single commodity flows. J. ACM 56 (4) (2009)
Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani
The detectability lemma and quantum gap amplification. STOC (2009)
Sanjeev Arora, Satish Rao, Umesh V. Vazirani
Expander flows, geometric embeddings and graph partitioning. J. ACM 56 (2) (2009)
Sanjeev Arora, Satish Rao, Umesh V. Vazirani
Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51 (10) (2008)
Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi
On partitioning graphs via single commodity flows. STOC (2008)
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani
AdWords and generalized online matching. J. ACM 54 (5) (2007)
Umesh V. Vazirani
Keynote Speech: Quantum Physics and the Nature of Computation. IPDPS (2007)
Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani
Quantum Algorithms for Hidden Nonlinear Structures. FOCS (2007)
Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani
Computing with highly mixed states. J. ACM 53 (3) (2006)
Rohit Khandekar, Satish Rao, Umesh V. Vazirani
Graph partitioning using single commodity flows. STOC (2006)
Umesh V. Vazirani
Quantum Physics and the Nature of Computation. HiPC (2005)
Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani
AdWords and Generalized On-line Matching. FOCS (2005)
Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani
Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem. Comb. 24 (1) (2004)
Sanjeev Arora, Satish Rao, Umesh V. Vazirani
Expander flows, geometric embeddings and graph partitioning. STOC (2004)
Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson
The Quantum Communication Complexity of Sampling. SIAM J. Comput. 32 (6) (2003)
Umesh V. Vazirani
Quantum Algorithms. LATIN (2002)
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
Dense quantum coding and quantum finite automata. J. ACM 49 (4) (2002)
Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani
Quantum mechanical algorithms for the nonabelian hidden subgroup problem. STOC (2001)
Wim van Dam, Michele Mosca, Umesh V. Vazirani
How Powerful is Adiabatic Quantum Computation?. FOCS (2001)
Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani
Quantum walks on graphs. STOC (2001)
Umesh V. Vazirani
Quantum Algorithms. FCT (2001)
Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao
Quantum bit escrow. STOC (2000)
Umesh V. Vazirani
Quantum computing and quantum complexity theory. ISCAS (2000)
Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani
Computing with highly mixed states (extended abstract). STOC (2000)
Umesh V. Vazirani
Fourier Transforms and Quantum Computation. Theoretical Aspects of Computer Science (2000)
Leonard J. Schulman, Umesh V. Vazirani
Molecular Scale Heat Engines and Scalable Quantum Computation. STOC (1999)
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. STOC (1999)
Umesh V. Vazirani
Go-With-The-Winners Heuristic. WADS (1999)
Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson
The Quantum Communication Complexity of Sampling. FOCS (1998)
Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani
Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata CoRR (1998)
Umesh V. Vazirani
Quantum Computation and Information. FSTTCS (1998)
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani
On Syntactic versus Computational Views of Approximability. SIAM J. Comput. 28 (1) (1998)
Ethan Bernstein, Umesh V. Vazirani
Quantum Complexity Theory. SIAM J. Comput. 26 (5) (1997)
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh V. Vazirani
Strengths and Weaknesses of Quantum Computing. SIAM J. Comput. 26 (5) (1997)
Umesh V. Vazirani
Introduction to Special Section on Quantum Computation. SIAM J. Comput. 26 (5) (1997)
Mark Jerrum, Umesh V. Vazirani
A Mildly Exponential Approximation Algorithm for the Permanent. Algorithmica 16 (4/5) (1996)
David J. Aldous, Umesh V. Vazirani
A Markovian Extension of Valiant's Learning Model Inf. Comput. 117 (2) (1995)
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani
On Syntactic versus Computational Views of Approximability Electron. Colloquium Comput. Complex. 2 (23) (1995)
Michael J. Kearns, Umesh V. Vazirani
Computational Learning Theory. SIGACT News 26 (1) (1995)
David J. Aldous, Umesh V. Vazirani
"Go With the Winners" Algorithms FOCS (1994)
Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani
On Syntactic versus Computational Views of Approximability FOCS (1994)
Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani
Simple and efficient leader election in the full information model. STOC (1994)
Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani
Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). STOC (1994)
William S. Evans, Sridhar Rajagopalan, Umesh V. Vazirani
Choosing a Reliable Hypothesis. COLT (1993)
Miklos Santha, Umesh V. Vazirani
Parallel searching of multidimensional cubes. Discret. Math. 114 (1-3) (1993)
Ethan Bernstein, Umesh V. Vazirani
Quantum complexity theory. STOC (1993)
Martin E. Dyer, Alan M. Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perkovic, Umesh V. Vazirani
A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem. Comb. Probab. Comput. 2 (1993)
Mark Jerrum, Umesh V. Vazirani
A Mildly Exponential Approximation Algorithm for the Permanent FOCS (1992)
Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani
An Optimal Algorithm for On-line Bipartite Matching STOC (1990)
David J. Aldous, Umesh V. Vazirani
A Markovian Extension of Valiant's Learning Model (Extended Abstract) FOCS (1990)
Nathan Linial, Umesh V. Vazirani
Graph Products and Chromatic Numbers FOCS (1989)
Umesh V. Vazirani, Vijay V. Vazirani
The Two-Processor Scheduling Problem is in Random NC. SIAM J. Comput. 18 (6) (1989)
Paul Dagum, Michael Luby, Milena Mihail, Umesh V. Vazirani
Polytopes, Permanents and Graphs with Large Factors FOCS (1988)
Ming Li, Umesh V. Vazirani
On the Learnability of Finite Automata. COLT (1988)
Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani
Matching is as easy as matrix inversion. Comb. 7 (1) (1987)
Umesh V. Vazirani
Strong communication complexity or generating quasirandom sequences form two communicating semi-random sources. Comb. 7 (4) (1987)
Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani
Matching Is as Easy as Matrix Inversion STOC (1987)
Umesh V. Vazirani
Efficiency Considerations in Using Semi-random Sources (Extended Abstract) STOC (1987)
Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani
Global Wire Routing in Two-Dimensional Arrays. Algorithmica 2 (1987)
Miklos Santha, Umesh V. Vazirani
Generating Quasi-random Sequences from Semi-random Sources. J. Comput. Syst. Sci. 33 (1) (1986)
Umesh V. Vazirani, Vijay V. Vazirani
Sampling a Population with a Semi-Random Source. FSTTCS (1986)
Umesh V. Vazirani, Vijay V. Vazirani
Random Polynomial Time Is Equal to Slightly-random Polynomial Time FOCS (1985)
Umesh V. Vazirani
Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract) STOC (1985)

Umesh V. Vazirani.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Umesh V. Vazirani