Umesh V. Vazirani

Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani: Multiplicative updates in coordination games and the theory of evolution. ITCS 2013: 57-58

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: 321-322

Umesh V. Vazirani, Thomas Vidick: Certifiable quantum dice: or, true random number generation secure against quantum adversaries. STOC 2012: 61-76

Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani: Multiplicative Updates in Coordination Games and the Theory of Evolution. CoRR abs/1208.3160 (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: 324-333

Umesh V. Vazirani: Quantum State Description Complexity (Invited Talk). FSTTCS 2011: 26-27

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2) (2009)

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: 417-426

Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh V. Vazirani: Algorithms. McGraw-Hill 2008, isbn 978-0-07-352340-8, pp. I-X, 1-320

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51(10): 96-105 (2008)

Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi: On partitioning graphs via single commodity flows. STOC 2008: 461-470

Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani: AdWords and generalized online matching. J. ACM 54(5) (2007)

Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani: Quantum Algorithms for Hidden Nonlinear Structures. FOCS 2007: 395-404

Umesh V. Vazirani: Keynote Speech: Quantum Physics and the Nature of Computation. IPDPS 2007: 15-16

Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani: Computing with highly mixed states. J. ACM 53(3): 507-531 (2006)

Rohit Khandekar, Satish Rao, Umesh V. Vazirani: Graph partitioning using single commodity flows. STOC 2006: 385-390

Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani: AdWords and Generalized On-line Matching. FOCS 2005: 264-273

Umesh V. Vazirani: Quantum Physics and the Nature of Computation. HiPC 2005: 6

Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani: Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem. Combinatorica 24(1): 137-154 (2004)

Sanjeev Arora, Satish Rao, Umesh V. Vazirani: Expander flows, geometric embeddings and graph partitioning. STOC 2004: 222-231

Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson: The Quantum Communication Complexity of Sampling. SIAM J. Comput. 32(6): 1570-1585 (2003)

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani: Dense quantum coding and quantum finite automata. J. ACM 49(4): 496-511 (2002)

Umesh V. Vazirani: Quantum Algorithms. LATIN 2002: 12-13

Umesh V. Vazirani: Quantum Algorithms. FCT 2001: 45-46

Wim van Dam, Michele Mosca, Umesh V. Vazirani: How Powerful is Adiabatic Quantum Computation?. FOCS 2001: 279-287

Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani: Quantum walks on graphs. STOC 2001: 50-59

Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani: Quantum mechanical algorithms for the nonabelian hidden subgroup problem. STOC 2001: 68-74

Umesh V. Vazirani: Fourier Transforms and Quantum Computation. Theoretical Aspects of Computer Science 2000: 208-220

Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani: Computing with highly mixed states (extended abstract). STOC 2000: 697-704

Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao: Quantum bit escrow. STOC 2000: 705-714

Leonard J. Schulman, Umesh V. Vazirani: Molecular Scale Heat Engines and Scalable Quantum Computation. STOC 1999: 322-329

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani: Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. STOC 1999: 376-383

Umesh V. Vazirani: Go-With-The-Winners Heuristic. WADS 1999: 217-218

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. SIAM J. Comput. 28(1): 164-191 (1998)

Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson: The Quantum Communication Complexity of Sampling. FOCS 1998: 342-351

Umesh V. Vazirani: Quantum Computation and Information. FSTTCS 1998: 367

Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani: Dense Quantum Coding and a Lower Bound for 1-way Quantum Automata. CoRR quant-ph/9804043 (1998)

Umesh V. Vazirani: Introduction to Special Section on Quantum Computation. SIAM J. Comput. 26(5): 1409-1410 (1997)

Ethan Bernstein, Umesh V. Vazirani: Quantum Complexity Theory. SIAM J. Comput. 26(5): 1411-1473 (1997)

Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh V. Vazirani: Strengths and Weaknesses of Quantum Computing. SIAM J. Comput. 26(5): 1510-1523 (1997)

Mark Jerrum, Umesh V. Vazirani: A Mildly Exponential Approximation Algorithm for the Permanent. Algorithmica 16(4/5): 392-401 (1996)

David Aldous, Umesh V. Vazirani: A Markovian Extension of Valiant's Learning Model. Inf. Comput. 117(2): 181-186 (1995)

Michael J. Kearns, Umesh V. Vazirani: Computational Learning Theory. SIGACT News 26(1): 43-45 (1995)

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. Electronic Colloquium on Computational Complexity (ECCC) 2(23) (1995)

David Aldous, Umesh V. Vazirani: ``Go With the Winners'' Algorithms. FOCS 1994: 492-501

Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani: On Syntactic versus Computational Views of Approximability. FOCS 1994: 819-830

Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani: Simple and efficient leader election in the full information model. STOC 1994: 234-242

Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani: Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). STOC 1994: 459-467

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. Combinatorics, Probability & Computing 2: 271-284 (1993)

Miklos Santha, Umesh V. Vazirani: Parallel searching of multidimensional cubes. Discrete Mathematics 114(1-3): 425-433 (1993)

William S. Evans, Sridhar Rajagopalan, Umesh V. Vazirani: Choosing a Reliable Hypothesis. COLT 1993: 269-276

Ethan Bernstein, Umesh V. Vazirani: Quantum complexity theory. STOC 1993: 11-20

Mark Jerrum, Umesh V. Vazirani: A Mildly Exponential Approximation Algorithm for the Permanent. FOCS 1992: 320-326

David Aldous, Umesh V. Vazirani: A Markovian Extension of Valiant's Learning Model (Extended Abstract). FOCS 1990: 392-396

Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani: An Optimal Algorithm for On-line Bipartite Matching. STOC 1990: 352-358

Umesh V. Vazirani, Vijay V. Vazirani: The Two-Processor Scheduling Problem is in Random NC. SIAM J. Comput. 18(6): 1140-1148 (1989)

Nathan Linial, Umesh V. Vazirani: Graph Products and Chromatic Numbers. FOCS 1989: 124-128

Ming Li, Umesh V. Vazirani: On the Learnability of Finite Automata. COLT 1988: 359-370

Paul Dagum, Michael Luby, Milena Mihail, Umesh V. Vazirani: Polytopes, Permanents and Graphs with Large Factors. FOCS 1988: 412-421

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: 113-129 (1987)

Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani: Matching is as easy as matrix inversion. Combinatorica 7(1): 105-113 (1987)

Umesh V. Vazirani: Strong communication complexity or generating quasirandom sequences form two communicating semi-random sources. Combinatorica 7(4): 375-392 (1987)

Umesh V. Vazirani: Efficiency Considerations in Using Semi-random Sources (Extended Abstract). STOC 1987: 160-168

Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani: Matching Is as Easy as Matrix Inversion. STOC 1987: 345-354

Miklos Santha, Umesh V. Vazirani: Generating Quasi-random Sequences from Semi-random Sources. J. Comput. Syst. Sci. 33(1): 75-87 (1986)

Umesh V. Vazirani, Vijay V. Vazirani: Sampling a Population with a Semi-Random Source. FSTTCS 1986: 443-452

Umesh V. Vazirani, Vijay V. Vazirani: Random Polynomial Time Is Equal to Slightly-random Polynomial Time. FOCS 1985: 417-428

Dexter Kozen, Umesh V. Vazirani, Vijay V. Vazirani: NC Algorithms for Comparability Graphs, Interval Gaphs, and Testing for Unique Perfect Matching. FSTTCS 1985: 496-503

Umesh V. Vazirani, Vijay V. Vazirani: The Two-Processor Scheduling Problem is in R-NC. STOC 1985: 11-21

Umesh V. Vazirani: Towards a Strong Communication Complexity Theory or Generating Quasi-Random Sequences from Two Communicating Slightly-random Sources (Extended Abstract). STOC 1985: 366-378

Christos H. Papadimitriou, Umesh V. Vazirani: On Two Geometric Problems Related to the Traveling Salesman Problem. J. Algorithms 5(2): 231-246 (1984)

Umesh V. Vazirani, Vijay V. Vazirani: Efficient and Secure Pseudo-Random Number Generation. CRYPTO 1984: 193-202

Miklos Santha, Umesh V. Vazirani: Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract). FOCS 1984: 434-440

Umesh V. Vazirani, Vijay V. Vazirani: Efficient and Secure Pseudo-Random Number Generation (Extended Abstract). FOCS 1984: 458-463

Umesh V. Vazirani, Vijay V. Vazirani: A Natural Encoding Scheme Proved Probabilistic Polynomial Complete. Theor. Comput. Sci. 24: 291-300 (1983)

Manuel Blum, Umesh V. Vazirani, Vijay V. Vazirani: Reducibility Among Protocols. CRYPTO 1983: 137-146

Umesh V. Vazirani, Vijay V. Vazirani: RSA Bits are 732+epsilon Secure. CRYPTO 1983: 369-375

Umesh V. Vazirani, Vijay V. Vazirani: Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design. FOCS 1983: 23-30

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 (Extended Abstract). FOCS 1983: 453-459

Umesh V. Vazirani, Vijay V. Vazirani: A Natural Encoding Scheme Proved Probabilistic Polynomial Complete. FOCS 1982: 40-44