| 2023 | STOC | A Polynomial-Time Classical Algorithm for Noisy Random Circuit Sampling. | Dorit Aharonov, Xun Gao, Zeph Landau, Yunchao Liu, Umesh V. Vazirani |
| 2022 | STOC | Deniable encryption in a Quantum world. | Andrea Coladangelo, Shafi Goldwasser, Umesh V. Vazirani |
| 2021 | STOC | (Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. | Andrs Gilyn, Matthew B. Hastings, Umesh V. Vazirani |
| 2018 | FOCS | 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 |
| 2018 | ICALP | Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States. | Chinmay Nirkhe, Umesh V. Vazirani, Henry Yuen |
| 2014 | FOCS | 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 |
| 2012 | STOC | Certifiable quantum dice: or, true random number generation secure against quantum adversaries. | Umesh V. Vazirani, Thomas Vidick |
| 2011 | FOCS | The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach. | Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani |
| 2009 | STOC | The detectability lemma and quantum gap amplification. | Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani |
| 2008 | STOC | On partitioning graphs via single commodity flows. | Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi |
| 2007 | FOCS | Quantum Algorithms for Hidden Nonlinear Structures. | Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani |
| 2006 | STOC | Graph partitioning using single commodity flows. | Rohit Khandekar, Satish Rao, Umesh V. Vazirani |
| 2005 | FOCS | AdWords and Generalized On-line Matching. | Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani |
| 2005 | HiPC | Quantum Physics and the Nature of Computation. | Umesh V. Vazirani |
| 2004 | STOC | Expander flows, geometric embeddings and graph partitioning. | Sanjeev Arora, Satish Rao, Umesh V. Vazirani |
| 2002 | LATIN | Quantum Algorithms. | Umesh V. Vazirani |
| 2001 | FCT | Quantum Algorithms. | Umesh V. Vazirani |
| 2001 | FOCS | How Powerful is Adiabatic Quantum Computation?. | Wim van Dam, Michele Mosca, Umesh V. Vazirani |
| 2001 | STOC | Quantum walks on graphs. | Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani |
| 2001 | STOC | Quantum mechanical algorithms for the nonabelian hidden subgroup problem. | Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani |
| 2000 | ISCAS | Quantum computing and quantum complexity theory. | Umesh V. Vazirani |
| 2000 | STOC | Quantum bit escrow. | Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao |
| 2000 | STOC | Computing with highly mixed states (extended abstract). | Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani |
| 1999 | STOC | Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. | Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani |
| 1999 | STOC | Molecular Scale Heat Engines and Scalable Quantum Computation. | Leonard J. Schulman, Umesh V. Vazirani |
| 1999 | WADS | Go-With-The-Winners Heuristic. | Umesh V. Vazirani |
| 1998 | FOCS | The Quantum Communication Complexity of Sampling. | Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson |
| 1994 | FOCS | "Go With the Winners" Algorithms | David J. Aldous, Umesh V. Vazirani |
| 1994 | FOCS | On Syntactic versus Computational Views of Approximability | Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani |
| 1994 | STOC | Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). | Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani |
| 1994 | STOC | Simple and efficient leader election in the full information model. | Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani |
| 1993 | COLT | Choosing a Reliable Hypothesis. | William S. Evans, Sridhar Rajagopalan, Umesh V. Vazirani |
| 1993 | STOC | Quantum complexity theory. | Ethan Bernstein, Umesh V. Vazirani |
| 1992 | FOCS | A Mildly Exponential Approximation Algorithm for the Permanent | Mark Jerrum, Umesh V. Vazirani |
| 1990 | FOCS | A Markovian Extension of Valiant's Learning Model (Extended Abstract) | David J. Aldous, Umesh V. Vazirani |
| 1990 | STOC | An Optimal Algorithm for On-line Bipartite Matching | Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani |
| 1989 | FOCS | Graph Products and Chromatic Numbers | Nathan Linial, Umesh V. Vazirani |
| 1988 | COLT | On the Learnability of Finite Automata. | Ming Li, Umesh V. Vazirani |
| 1988 | FOCS | Polytopes, Permanents and Graphs with Large Factors | Paul Dagum, Michael Luby, Milena Mihail, Umesh V. Vazirani |
| 1987 | STOC | Matching Is as Easy as Matrix Inversion | Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani |
| 1987 | STOC | Efficiency Considerations in Using Semi-random Sources (Extended Abstract) | Umesh V. Vazirani |
| 1985 | FOCS | Random Polynomial Time Is Equal to Slightly-random Polynomial Time | Umesh V. Vazirani, Vijay V. Vazirani |
| 1985 | STOC | Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract) | Umesh V. Vazirani |
| 1985 | STOC | The Two-Processor Scheduling Problem is in R-NC | Umesh V. Vazirani, Vijay V. Vazirani |
| 1984 | CRYPTO | Efficient and Secure Pseudo-Random Number Generation. | Umesh V. Vazirani, Vijay V. Vazirani |
| 1984 | FOCS | Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract) | Miklos Santha, Umesh V. Vazirani |
| 1984 | FOCS | Efficient and Secure Pseudo-Random Number Generation (Extended Abstract) | Umesh V. Vazirani, Vijay V. Vazirani |
| 1983 | CRYPTO | RSA Bits are 732+epsilon Secure. | Umesh V. Vazirani, Vijay V. Vazirani |
| 1983 | CRYPTO | Reducibility Among Protocols. | Manuel Blum, Umesh V. Vazirani, Vijay V. Vazirani |
| 1983 | FOCS | 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 |
| 1983 | FOCS | Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design | Umesh V. Vazirani, Vijay V. Vazirani |
| 1982 | FOCS | A Natural Encoding Scheme Proved Probabilistic Polynomial Complete | Umesh V. Vazirani, Vijay V. Vazirani |