Umesh V. Vazirani

According to our database, Umesh V. Vazirani authored at least 95 papers between 1983 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Quantum Pseudoentanglement.

Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Public-key pseudoentanglement and the hardness of learning ground state entanglement structure.

Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou

CoRR, 2023

A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling.

Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh V. Vazirani

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

Quantum Pseudoentanglement.

Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Zixin Zhou

CoRR, 2022

Efficient Certifiable Randomness from a Single Quantum Device.

Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick

CoRR, 2022

Deniable encryption in a Quantum world.

Andrea Coladangelo, Shafi Goldwasser, Umesh V. Vazirani

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

2021

A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device.

Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick

J. ACM, 2021

Classically-Verifiable Quantum Advantage from a Computational Bell Test.

Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, Norman Y. Yao

CoRR, 2021

(Sub)Exponential advantage of adiabatic Quantum computation with no sign problem.

András Gilyén, Matthew B. Hastings, Umesh V. Vazirani

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

(Sub)Exponential advantage of adiabatic quantum computation with no sign problem.

András Gilyén, Umesh V. Vazirani

CoRR, 2020

Simpler Proofs of Quantumness.

Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick

Proceedings of the 15th Conference on the Theory of Quantum Computation, 2020

Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract).

Adam Bouland, Bill Fefferman, Umesh V. Vazirani

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

The duality gap for two-team zero-sum games.

Leonard J. Schulman, Umesh V. Vazirani

Games Econ. Behav., 2019

Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality.

Adam Bouland, Bill Fefferman, Umesh V. Vazirani

CoRR, 2019

Fully device independent quantum key distribution.

Umesh V. Vazirani, Thomas Vidick

Commun. ACM, 2019

"Quantum Supremacy" and the Complexity of Random Circuit Sampling.

Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

2018

Certifiable Randomness from a Single Quantum Device.

Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick

CoRR, 2018

Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States.

Chinmay Nirkhe, Umesh V. Vazirani, Henry Yuen

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

2017

Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D.

Itai Arad, Zeph Landau, Umesh V. Vazirani, Thomas Vidick

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2014

Algorithms, games, and evolution.

Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani

Proc. Natl. Acad. Sci. USA, 2014

Robust device independent quantum key distribution.

Umesh V. Vazirani, Thomas Vidick

Proceedings of the Innovations in Theoretical Computer Science, 2014

An efficient algorithm for finding the ground state of 1D gapped local hamiltonians.

Zeph Landau, Umesh V. Vazirani, Thomas Vidick

Proceedings of the Innovations in Theoretical Computer Science, 2014

Algorithms, Games, and Evolution (Invited Talk).

Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani

Proceedings of the 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, 2014

Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law.

Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

2013

Classical command of quantum systems.

Ben W. Reichardt, Falk Unger, Umesh V. Vazirani

Nat., 2013

A classical leash for a quantum system: command of quantum systems via rigidity of CHSH games.

Ben W. Reichardt, Falk Unger, Umesh V. Vazirani

Proceedings of the Innovations in Theoretical Computer Science, 2013

Multiplicative updates in coordination games and the theory of evolution.

Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani

Proceedings of the Innovations in Theoretical Computer Science, 2013

2012

Certifiable quantum dice: or, true random number generation secure against quantum adversaries.

Umesh V. Vazirani, Thomas Vidick

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

Quantum State Description Complexity (Invited Talk).

Umesh V. Vazirani

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2011

The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach.

Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2009

Graph partitioning using single commodity flows.

Rohit Khandekar, Satish Rao, Umesh V. Vazirani

J. ACM, 2009

Expander flows, geometric embeddings and graph partitioning.

Sanjeev Arora, Satish Rao, Umesh V. Vazirani

J. ACM, 2009

The detectability lemma and quantum gap amplification.

Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

Geometry, flows, and graph-partitioning algorithms.

Sanjeev Arora, Satish Rao, Umesh V. Vazirani

Commun. ACM, 2008

On partitioning graphs via single commodity flows.

Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Algorithms.

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh V. Vazirani

McGraw-Hill, ISBN: 978-0-07-352340-8, 2008

2007

AdWords and generalized online matching.

Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani

J. ACM, 2007

Keynote Speech: Quantum Physics and the Nature of Computation.

Umesh V. Vazirani

Proceedings of the 21th International Parallel and Distributed Processing Symposium (IPDPS 2007), 2007

Quantum Algorithms for Hidden Nonlinear Structures.

Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

2006

Computing with highly mixed states.

Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani

J. ACM, 2006

2005

Quantum Physics and the Nature of Computation.

Umesh V. Vazirani

Proceedings of the High Performance Computing, 2005

AdWords and Generalized On-line Matching.

Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

2004

Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem.

Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani

Comb., 2004

2003

The Quantum Communication Complexity of Sampling.

Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson

SIAM J. Comput., 2003

2002

Dense quantum coding and quantum finite automata.

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani

J. ACM, 2002

2001

Quantum walks on graphs.

Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

How Powerful is Adiabatic Quantum Computation?.

Wim van Dam, Michele Mosca, Umesh V. Vazirani

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Quantum Algorithms.

Umesh V. Vazirani

Proceedings of the Fundamentals of Computation Theory, 13th International Symposium, 2001

2000

Computing with highly mixed states (extended abstract).

Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Quantum bit escrow.

Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Quantum computing and quantum complexity theory.

Umesh V. Vazirani

Proceedings of the IEEE International Symposium on Circuits and Systems, 2000

Fourier Transforms and Quantum Computation.

Umesh V. Vazirani

Proceedings of the Theoretical Aspects of Computer Science, 2000

1999

Go-With-The-Winners Heuristic.

Umesh V. Vazirani

Proceedings of the Algorithms and Data Structures, 6th International Workshop, 1999

Molecular Scale Heat Engines and Scalable Quantum Computation.

Leonard J. Schulman, Umesh V. Vazirani

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata.

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Quantum Computation and Information.

Umesh V. Vazirani

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1998

1997

Introduction to Special Section on Quantum Computation.

Umesh V. Vazirani

SIAM J. Comput., 1997

Quantum Complexity Theory.

Ethan Bernstein, Umesh V. Vazirani

SIAM J. Comput., 1997

Strengths and Weaknesses of Quantum Computing.

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh V. Vazirani

SIAM J. Comput., 1997

1996

A Mildly Exponential Approximation Algorithm for the Permanent.

Mark Jerrum, Umesh V. Vazirani

Algorithmica, 1996

1995

A Markovian Extension of Valiant's Learning Model

David J. Aldous, Umesh V. Vazirani

Inf. Comput., March, 1995

Computational Learning Theory.

Michael J. Kearns, Umesh V. Vazirani

SIGACT News, 1995

On Syntactic versus Computational Views of Approximability

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani

Electron. Colloquium Comput. Complex., 1995

1994

Simple and efficient leader election in the full information model.

Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Simulating quadratic dynamical systems is PSPACE-complete (preliminary version).

Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

"Go With the Winners" Algorithms

David J. Aldous, Umesh V. Vazirani

Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

An Introduction to Computational Learning Theory.

Michael J. Kearns, Umesh V. Vazirani

MIT Press, ISBN: 978-0-262-11193-5, 1994

1993

Parallel searching of multidimensional cubes.

Miklos Santha, Umesh V. Vazirani

Discret. Math., 1993

A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem.

Martin E. Dyer, Alan M. Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perkovic, Umesh V. Vazirani

Comb. Probab. Comput., 1993

Choosing a Reliable Hypothesis.

William S. Evans, Sridhar Rajagopalan, Umesh V. Vazirani

Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1990

An Optimal Algorithm for On-line Bipartite Matching

Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

A Markovian Extension of Valiant's Learning Model (Extended Abstract)

David J. Aldous, Umesh V. Vazirani

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1989

The Two-Processor Scheduling Problem is in Random NC.

Umesh V. Vazirani, Vijay V. Vazirani

SIAM J. Comput., 1989

Graph Products and Chromatic Numbers

Nathan Linial, Umesh V. Vazirani

Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 1989

1988

Polytopes, Permanents and Graphs with Large Factors

Paul Dagum, Michael Luby, Milena Mihail, Umesh V. Vazirani

Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988

On the Learnability of Finite Automata.

Ming Li, Umesh V. Vazirani

Proceedings of the First Annual Workshop on Computational Learning Theory, 1988

1987

Strong communication complexity or generating quasirandom sequences form two communicating semi-random sources.

Umesh V. Vazirani

Comb., 1987

Matching is as easy as matrix inversion.

Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani

Comb., 1987

Global Wire Routing in Two-Dimensional Arrays.

Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani

Algorithmica, 1987

Efficiency Considerations in Using Semi-random Sources (Extended Abstract)

Umesh V. Vazirani

Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987

1986

Generating Quasi-random Sequences from Semi-random Sources.

Miklos Santha, Umesh V. Vazirani

J. Comput. Syst. Sci., 1986

Sampling a Population with a Semi-Random Source.

Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1986

1985

The Two-Processor Scheduling Problem is in R-NC

Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract)

Umesh V. Vazirani

Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985

NC Algorithms for Comparability Graphs, Interval Gaphs, and Testing for Unique Perfect Matching.

Dexter Kozen, Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1985

Random Polynomial Time Is Equal to Slightly-random Polynomial Time

Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 26th Annual Symposium on Foundations of Computer Science, 1985

1984

On Two Geometric Problems Related to the Traveling Salesman Problem.

Christos H. Papadimitriou, Umesh V. Vazirani

J. Algorithms, 1984

Efficient and Secure Pseudo-Random Number Generation (Extended Abstract)

Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract)

Miklos Santha, Umesh V. Vazirani

Proceedings of the 25th Annual Symposium on Foundations of Computer Science, 1984

Efficient and Secure Pseudo-Random Number Generation.

Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the Advances in Cryptology, 1984

1983

A Natural Encoding Scheme Proved Probabilistic Polynomial Complete.

Umesh V. Vazirani, Vijay V. Vazirani

Theor. Comput. Sci., 1983

Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design

Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)

Richard M. Karp, Frank Thomson Leighton, Ronald L. Rivest, Clark D. Thompson, Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the 24th Annual Symposium on Foundations of Computer Science, 1983

Reducibility Among Protocols.

Manuel Blum, Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the Advances in Cryptology, 1983

RSA Bits are 732+epsilon Secure.

Umesh V. Vazirani, Vijay V. Vazirani

Proceedings of the Advances in Cryptology, 1983