Umesh V. Vazirani

114 papers A* 47A 12B 3C 1Misc 1Journal 42Unranked 6

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