Umesh Vazirani - Publications

Affiliations: 
Electrical Engineering and Computer Science University of California, Berkeley, Berkeley, CA, United States 
Area:
Security (SEC); Theory (THY), Complexity theory

44 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2019 Vazirani U, Vidick T. Fully device independent quantum key distribution Communications of the Acm. 62: 133-133. DOI: 10.1145/3310974  0.417
2018 Bouland A, Fefferman B, Nirkhe C, Vazirani U. On the complexity and verification of quantum random circuit sampling Nature Physics. 15: 159-163. DOI: 10.1038/S41567-018-0318-2  0.442
2017 Arad I, Landau Z, Vazirani U, Vidick T. Rigorous RG Algorithms and Area Laws for Low Energy Eigenstates in 1D Communications in Mathematical Physics. 356: 65-105. DOI: 10.1007/S00220-017-2973-Z  0.405
2016 Vazirani U, Vidick T. Erratum: Fully Device-Independent Quantum Key Distribution [Phys. Rev. Lett. 113, 140501 (2014)]. Physical Review Letters. 116: 089901. PMID 26967446 DOI: 10.1103/Physrevlett.116.089901  0.368
2015 Landau Z, Vazirani U, Vidick T. A polynomial time algorithm for the ground state of one-dimensional gapped local Hamiltonians Nature Physics. 11: 566-569. DOI: 10.1038/Nphys3345  0.384
2014 Vazirani U, Vidick T. Fully device-independent quantum key distribution. Physical Review Letters. 113: 140501. PMID 25325625 DOI: 10.1103/Physrevlett.113.140501  0.401
2014 Aharonov D, Harrow AW, Landau Z, Nagaj D, Szegedy M, Vazirani U. Local tests of global entanglement and a counterexample to the generalized area law Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 246-255. DOI: 10.1109/FOCS.2014.34  0.31
2013 Reichardt BW, Unger F, Vazirani U. Classical command of quantum systems. Nature. 496: 456-60. PMID 23619692 DOI: 10.1038/nature12035  0.678
2012 Vazirani U, Vidick T. Certifiable quantum dice. Philosophical Transactions. Series a, Mathematical, Physical, and Engineering Sciences. 370: 3432-48. PMID 22711867 DOI: 10.1098/Rsta.2011.0336  0.406
2012 Vazirani U, Vidick T. Certifiable quantum dice: Or, true random number generation secure against quantum adversaries Proceedings of the Annual Acm Symposium On Theory of Computing. 61-76. DOI: 10.1145/2213977.2213984  0.3
2011 Aharonov D, Arad I, Vazirani U, Landau Z. The detectability lemma and its applications to Quantum Hamiltonian complexity New Journal of Physics. 13. DOI: 10.1088/1367-2630/13/11/113043  0.402
2009 Khandekar R, Rao S, Vazirani U. Graph partitioning using single commodity flows Journal of the Acm. 56. DOI: 10.1145/1538902.1538903  0.363
2009 Arora S, Rao S, Vazirani U. Expander flows, geometric embeddings and graph partitioning Journal of the Acm. 56. DOI: 10.1145/1502793.1502794  0.573
2008 Arora S, Rao S, Vazirani U. Geometry, flows, and graph-partitioning algorithms Communications of the Acm. 51: 96-105. DOI: 10.1145/1400181.1400204  0.564
2007 Mehta A, Saberi A, Vazirani U, Vazirani V. AdWords and generalized online matching Journal of the Acm. 54. DOI: 10.1145/1284320.1284321  0.612
2007 Childs AM, Schulman LJ, Vazirani UV. Quantum algorithms for hidden nonlinear structures Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 395-404. DOI: 10.1109/FOCS.2007.4389510  0.381
2006 Ambainis A, Schulman LJ, Vazirani U. Computing with highly mixed states Journal of the Acm. 53: 507-531. DOI: 10.1145/1147954.1147962  0.622
2005 Mehta A, Saberi A, Vazirani U, Vazirani V. AdWords and generalized on-line matching Proceedings - Annual Ieee Symposium On Foundations of Computer Science, Focs. 2005: 264-273. DOI: 10.1109/SFCS.2005.12  0.584
2005 Vala J, Thapliyal AV, Myrgren S, Vazirani U, Weiss DS, Whaley KB. Perfect pattern formation of neutral atoms in an addressable optical lattice Physical Review a - Atomic, Molecular, and Optical Physics. 71. DOI: 10.1103/Physreva.71.032324  0.36
2005 Vazirani U. Quantum physics and the nature of computation Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 3769: 6.  0.348
2004 Grigni M, Schulman LJ, Vazirani M, Vazirani U. Quantum mechanical algorithms for the nonabelian hidden subgroup problem Combinatorica. 24: 137-154. DOI: 10.1007/S00493-004-0009-8  0.457
2003 Ambainis A, Schulman LJ, Ta-Shma A, Vazirani U, Wigderson A. The quantum communication complexity of sampling Siam Journal On Computing. 32: 1570-1585. DOI: 10.1137/S009753979935476  0.608
2002 Ambainis A, Nayak A, Ta-Shma A, Vazirani U. Dense quantum coding and quantum finite automata Journal of the Acm. 49: 496-511. DOI: 10.1145/581771.581773  0.648
2001 Van Dam W, Mosca M, Vazirani U. How powerful is adiabatic quantum computation? Annual Symposium On Foundations of Computer Science - Proceedings. 279-287.  0.391
2001 Aharonov D, Ambainis A, Kempe J, Vazirani U. Quantum walks on graphs Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 50-59.  0.61
2000 Aharonov D, Ta-Shma A, Vazirani UV, Yao AC. Quantum bit escrow Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 705-714.  0.33
2000 Vazirani U. Quantum computing and quantum complexity theory Proceedings - Ieee International Symposium On Circuits and Systems. 1: I-737-I-739.  0.325
1999 Khanna S, Motwani R, Sudan M, Vazirani U. On Syntactic versus Computational Views of Approximability Siam Journal On Computing. 28: 164-191. DOI: 10.1137/S0097539795286612  0.636
1999 Ambainis A, Nayak A, Ta-Shma A, Vazirani U. Dense quantum coding and a lower bound for 1-way quantum automata Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 376-383.  0.618
1999 Schulman LJ, Vazirani UV. Molecular scale heat engines and scalable quantum computation Conference Proceedings of the Annual Acm Symposium On Theory of Computing. 322-329.  0.318
1998 Vazirani U. On the power of quantum computation Philosophical Transactions of the Royal Society a: Mathematical, Physical and Engineering Sciences. 356: 1759-1768. DOI: 10.1098/Rsta.1998.0247  0.485
1997 Vazirani U. Introduction to Special Section on Quantum Computation Siam Journal On Computing. 26: 1409-1410. DOI: 10.1137/Smjcat000026000005001409000001  0.486
1997 Bennett CH, Bernstein E, Brassard G, Vazirani U. Strengths and weaknesses of quantum computing Siam Journal On Computing. 26: 1510-1523. DOI: 10.1137/S0097539796300933  0.439
1997 Bernstein E, Vazirani U. Quantum complexity theory Siam Journal On Computing. 26: 1411-1473. DOI: 10.1137/S0097539796300921  0.43
1990 Karp RM, Vazirani UV, Vazirani VV. Optimal algorithm for on-line bipartite matching . 352-358.  0.558
1989 Vazirani UV, Vazirani VV. Two-processor scheduling problem is in random NC Siam Journal On Computing. 18: 1140-1148.  0.614
1989 Linial N, Vazirani U. Graph products and chromatic numbers Annual Symposium On Foundations of Computer Science (Proceedings). 124-128.  0.301
1987 Vazirani UV. Strong communication complexity or generating quasi-random sequences from two communicating semi-random sources Combinatorica. 7: 375-392. DOI: 10.1007/Bf02579325  0.309
1987 Mulmuley K, Vazirani UV, Vazirani VV. Matching is as easy as matrix inversion Combinatorica. 7: 105-113. DOI: 10.1007/Bf02579206  0.595
1987 Karp RM, Leighton FT, Rivest RL, Thompson CD, Vazirani UV, Vazirani VV. Global wire routing in two-dimensional arrays Algorithmica. 2: 113-129. DOI: 10.1007/BF01840353  0.509
1985 Vazirani UV, Vazirani VV. RANDOM POLYNOMIAL TIME IS EQUAL TO SLIGHTLY-RANDOM POLYNOMIAL TIME Annual Symposium On Foundations of Computer Science (Proceedings). 417-428.  0.568
1984 Vazirani UV, Vazirani VV. EFFICIENT AND SECURE PSEUDO-RANDOM NUMBER GENERATION Annual Symposium On Foundations of Computer Science (Proceedings). 458-463.  0.55
1983 Vazirani UV, Vazirani VV. A natural encoding scheme proved probabilistic polynomial complete Theoretical Computer Science. 24: 291-300. DOI: 10.1016/0304-3975(83)90004-X  0.559
1983 Vazirani UV, Vazirani VV. TRAPDOOR PSEUDO-RANDOM NUMBER GENERATORS, WITH APPLICATIONS TO PROTOCOL DESIGN Annual Symposium On Foundations of Computer Science (Proceedings). 23-30.  0.53
Show low-probability matches.