Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDUmesh V. Vazirani
Person information
- affiliation: University of California, Berkeley, USA
- award (2012): Fulkerson Prize
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2022
[c67]Andrea Coladangelo, Shafi Goldwasser, Umesh V. Vazirani:
Deniable encryption in a Quantum world. STOC 2022: 1378-1391- [i12]Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick:
Efficient Certifiable Randomness from a Single Quantum Device. CoRR abs/2204.11353 (2022) - [i11]Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Zixin Zhou
:
Quantum Pseudoentanglement. CoRR abs/2211.00747 (2022) - 2021
- [j29]Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick:
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. J. ACM 68(5): 31:1-31:47 (2021) - [c66]András Gilyén, Matthew B. Hastings, Umesh V. Vazirani:
(Sub)Exponential advantage of adiabatic Quantum computation with no sign problem. STOC 2021: 1357-1369 - [i10]Gregory D. Kahanamoku-Meyer, Soonwon Choi, Umesh V. Vazirani, Norman Y. Yao:
Classically-Verifiable Quantum Advantage from a Computational Bell Test. CoRR abs/2104.00687 (2021) - [i9]Andrea Coladangelo, Shafi Goldwasser, Umesh V. Vazirani:
Deniable Encryption in a Quantum World. CoRR abs/2112.14988 (2021) - 2020
- [c65]Adam Bouland, Bill Fefferman, Umesh V. Vazirani:
Computational Pseudorandomness, the Wormhole Growth Paradox, and Constraints on the AdS/CFT Duality (Abstract). ITCS 2020: 63:1-63:2 - [c64]Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick:
Simpler Proofs of Quantumness. TQC 2020: 8:1-8:14 - [i8]Zvika Brakerski, Venkata Koppula, Umesh V. Vazirani, Thomas Vidick:
Simpler Proofs of Quantumness. CoRR abs/2005.04826 (2020) - [i7]András Gilyén, Umesh V. Vazirani:
(Sub)Exponential advantage of adiabatic quantum computation with no sign problem. CoRR abs/2011.09495 (2020)
2010 – 2019
- 2019
- [j28]Umesh V. Vazirani, Thomas Vidick:
Fully device independent quantum key distribution. Commun. ACM 62(4): 133 (2019) - [j27]Leonard J. Schulman, Umesh V. Vazirani:
The duality gap for two-team zero-sum games. Games Econ. Behav. 115: 336-345 (2019) - [c63]Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani:
"Quantum Supremacy" and the Complexity of Random Circuit Sampling. ITCS 2019: 15:1-15:2 - [i6]Adam Bouland, Bill Fefferman, Umesh V. Vazirani:
Computational pseudorandomness, the wormhole growth paradox, and constraints on the AdS/CFT duality. CoRR abs/1910.14646 (2019) - 2018
- [c62]Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick:
A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. FOCS 2018: 320-331 - [c61]Chinmay Nirkhe, Umesh V. Vazirani, Henry Yuen:
Approximate Low-Weight Check Codes and Circuit Lower Bounds for Noisy Ground States. ICALP 2018: 91:1-91:11 - [i5]Adam Bouland, Bill Fefferman, Chinmay Nirkhe, Umesh V. Vazirani:
Quantum Supremacy and the Complexity of Random Circuit Sampling. CoRR abs/1803.04402 (2018) - [i4]Zvika Brakerski, Paul F. Christiano, Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick:
Certifiable Randomness from a Single Quantum Device. CoRR abs/1804.00640 (2018) - 2017
- [c60]Itai Arad, Zeph Landau, Umesh V. Vazirani, Thomas Vidick:
Rigorous Rg Algorithms and Area Laws for Low Energy Eigenstates In 1D. ITCS 2017: 46:1-46:14 - [c59]Leonard J. Schulman, Umesh V. Vazirani:
The Duality Gap for Two-Team Zero-Sum Games. ITCS 2017: 56:1-56:8 - 2014
- [j26]Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani:
Algorithms, games, and evolution. Proc. Natl. Acad. Sci. USA 111(29): 10620-10623 (2014) - [c58]Dorit Aharonov, Aram W. Harrow, Zeph Landau, Daniel Nagaj, Mario Szegedy, Umesh V. Vazirani:
Local Tests of Global Entanglement and a Counterexample to the Generalized Area Law. FOCS 2014: 246-255 - [c57]Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani:
Algorithms, Games, and Evolution (Invited Talk). FSTTCS 2014: 45-46 - [c56]Umesh V. Vazirani, Thomas Vidick:
Robust device independent quantum key distribution. ITCS 2014: 35-36 - [c55]Zeph Landau, Umesh V. Vazirani, Thomas Vidick:
An efficient algorithm for finding the ground state of 1D gapped local hamiltonians. ITCS 2014: 301-302 - 2013
- [j25]Ben W. Reichardt, Falk Unger, Umesh V. Vazirani:
Classical command of quantum systems. Nat. 496(7446): 456-460 (2013) - [c54]Erick Chastain, Adi Livnat, Christos H. Papadimitriou, Umesh V. Vazirani:
Multiplicative updates in coordination games and the theory of evolution. ITCS 2013: 57-58 - [c53]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 - 2012
- [c52]Umesh V. Vazirani, Thomas Vidick:
Certifiable quantum dice: or, true random number generation secure against quantum adversaries. STOC 2012: 61-76 - [i3]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) - 2011
- [c51]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 - [c50]Umesh V. Vazirani:
Quantum State Description Complexity (Invited Talk). FSTTCS 2011: 26-27
2000 – 2009
- 2009
- [j24]Sanjeev Arora, Satish Rao, Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning. J. ACM 56(2): 5:1-5:37 (2009) - [j23]Rohit Khandekar, Satish Rao, Umesh V. Vazirani:
Graph partitioning using single commodity flows. J. ACM 56(4): 19:1-19:15 (2009) - [c49]Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani:
The detectability lemma and quantum gap amplification. STOC 2009: 417-426 - 2008
- [b2]Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh V. Vazirani:
Algorithms. McGraw-Hill 2008, ISBN 978-0-07-352340-8, pp. I-X, 1-320 - [j22]Sanjeev Arora, Satish Rao, Umesh V. Vazirani:
Geometry, flows, and graph-partitioning algorithms. Commun. ACM 51(10): 96-105 (2008) - [c48]Lorenzo Orecchia, Leonard J. Schulman, Umesh V. Vazirani, Nisheeth K. Vishnoi:
On partitioning graphs via single commodity flows. STOC 2008: 461-470 - 2007
- [j21]Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani:
AdWords and generalized online matching. J. ACM 54(5): 22 (2007) - [c47]Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani:
Quantum Algorithms for Hidden Nonlinear Structures. FOCS 2007: 395-404 - [c46]Umesh V. Vazirani:
Keynote Speech: Quantum Physics and the Nature of Computation. IPDPS 2007: 15-16 - 2006
- [j20]Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani:
Computing with highly mixed states. J. ACM 53(3): 507-531 (2006) - [c45]Rohit Khandekar, Satish Rao, Umesh V. Vazirani:
Graph partitioning using single commodity flows. STOC 2006: 385-390 - 2005
- [c44]Aranyak Mehta, Amin Saberi, Umesh V. Vazirani, Vijay V. Vazirani:
AdWords and Generalized On-line Matching. FOCS 2005: 264-273 - [c43]Umesh V. Vazirani:
Quantum Physics and the Nature of Computation. HiPC 2005: 6 - 2004
- [j19]Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani:
Quantum Mechanical Algorithms for the Nonabelian Hidden Subgroup Problem. Comb. 24(1): 137-154 (2004) - [c42]Sanjeev Arora, Satish Rao, Umesh V. Vazirani:
Expander flows, geometric embeddings and graph partitioning. STOC 2004: 222-231 - 2003
- [j18]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) - 2002
- [j17]Andris Ambainis, Ashwin Nayak, Amnon Ta-Shma, Umesh V. Vazirani:
Dense quantum coding and quantum finite automata. J. ACM 49(4): 496-511 (2002) - [c41]Umesh V. Vazirani:
Quantum Algorithms. LATIN 2002: 12-13 - 2001
- [c40]Umesh V. Vazirani:
Quantum Algorithms. FCT 2001: 45-46 - [c39]Wim van Dam, Michele Mosca, Umesh V. Vazirani:
How Powerful is Adiabatic Quantum Computation?. FOCS 2001: 279-287 - [c38]Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani:
Quantum walks on graphs. STOC 2001: 50-59 - [c37]Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani:
Quantum mechanical algorithms for the nonabelian hidden subgroup problem. STOC 2001: 68-74 - 2000
- [c36]Umesh V. Vazirani:
Fourier Transforms and Quantum Computation. Theoretical Aspects of Computer Science 2000: 208-220 - [c35]Umesh V. Vazirani:
Quantum computing and quantum complexity theory. ISCAS 2000: 737-739 - [c34]Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani:
Computing with highly mixed states (extended abstract). STOC 2000: 697-704 - [c33]Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao:
Quantum bit escrow. STOC 2000: 705-714
1990 – 1999
- 1999
- [c32]Leonard J. Schulman, Umesh V. Vazirani:
Molecular Scale Heat Engines and Scalable Quantum Computation. STOC 1999: 322-329 - [c31]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 - [c30]Umesh V. Vazirani:
Go-With-The-Winners Heuristic. WADS 1999: 217-218 - 1998
- [j16]Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. SIAM J. Comput. 28(1): 164-191 (1998) - [c29]Andris Ambainis, Leonard J. Schulman, Amnon Ta-Shma, Umesh V. Vazirani, Avi Wigderson:
The Quantum Communication Complexity of Sampling. FOCS 1998: 342-351 - [c28]Umesh V. Vazirani:
Quantum Computation and Information. FSTTCS 1998: 367 - [i2]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) - 1997
- [j15]Umesh V. Vazirani:
Introduction to Special Section on Quantum Computation. SIAM J. Comput. 26(5): 1409-1410 (1997) - [j14]Ethan Bernstein, Umesh V. Vazirani:
Quantum Complexity Theory. SIAM J. Comput. 26(5): 1411-1473 (1997) - [j13]Charles H. Bennett, Ethan Bernstein, Gilles Brassard, Umesh V. Vazirani:
Strengths and Weaknesses of Quantum Computing. SIAM J. Comput. 26(5): 1510-1523 (1997) - 1996
- [j12]Mark Jerrum, Umesh V. Vazirani:
A Mildly Exponential Approximation Algorithm for the Permanent. Algorithmica 16(4/5): 392-401 (1996) - 1995
- [j11]David J. Aldous, Umesh V. Vazirani:
A Markovian Extension of Valiant's Learning Model. Inf. Comput. 117(2): 181-186 (1995) - [j10]Michael J. Kearns, Umesh V. Vazirani:
Computational Learning Theory. SIGACT News 26(1): 43-45 (1995) - [i1]Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. Electron. Colloquium Comput. Complex. TR95 (1995) - 1994
- [b1]Michael J. Kearns, Umesh V. Vazirani:
An Introduction to Computational Learning Theory. MIT Press 1994, ISBN 978-0-262-11193-5, pp. I-XII, 1-207 - [c27]David J. Aldous, Umesh V. Vazirani:
"Go With the Winners" Algorithms. FOCS 1994: 492-501 - [c26]Sanjeev Khanna, Rajeev Motwani, Madhu Sudan, Umesh V. Vazirani:
On Syntactic versus Computational Views of Approximability. FOCS 1994: 819-830 - [c25]Rafail Ostrovsky, Sridhar Rajagopalan, Umesh V. Vazirani:
Simple and efficient leader election in the full information model. STOC 1994: 234-242 - [c24]Sanjeev Arora, Yuval Rabani, Umesh V. Vazirani:
Simulating quadratic dynamical systems is PSPACE-complete (preliminary version). STOC 1994: 459-467 - 1993
- [j9]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. Comb. Probab. Comput. 2: 271-284 (1993) - [j8]Miklos Santha, Umesh V. Vazirani:
Parallel searching of multidimensional cubes. Discret. Math. 114(1-3): 425-433 (1993) - [c23]William S. Evans, Sridhar Rajagopalan, Umesh V. Vazirani:
Choosing a Reliable Hypothesis. COLT 1993: 269-276 - [c22]Ethan Bernstein, Umesh V. Vazirani:
Quantum complexity theory. STOC 1993: 11-20 - 1992
- [c21]Mark Jerrum, Umesh V. Vazirani:
A Mildly Exponential Approximation Algorithm for the Permanent. FOCS 1992: 320-326 - 1990
- [c20]David J. Aldous, Umesh V. Vazirani:
A Markovian Extension of Valiant's Learning Model (Extended Abstract). FOCS 1990: 392-396 - [c19]Richard M. Karp, Umesh V. Vazirani, Vijay V. Vazirani:
An Optimal Algorithm for On-line Bipartite Matching. STOC 1990: 352-358
1980 – 1989
- 1989
- [j7]Umesh V. Vazirani, Vijay V. Vazirani:
The Two-Processor Scheduling Problem is in Random NC. SIAM J. Comput. 18(6): 1140-1148 (1989) - [c18]Nathan Linial, Umesh V. Vazirani:
Graph Products and Chromatic Numbers. FOCS 1989: 124-128 - 1988
- [c17]Ming Li, Umesh V. Vazirani:
On the Learnability of Finite Automata. COLT 1988: 359-370 - [c16]Paul Dagum, Michael Luby, Milena Mihail, Umesh V. Vazirani:
Polytopes, Permanents and Graphs with Large Factors. FOCS 1988: 412-421 - 1987
- [j6]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) - [j5]Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani:
Matching is as easy as matrix inversion. Comb. 7(1): 105-113 (1987) - [j4]Umesh V. Vazirani:
Strong communication complexity or generating quasirandom sequences form two communicating semi-random sources. Comb. 7(4): 375-392 (1987) - [c15]Umesh V. Vazirani:
Efficiency Considerations in Using Semi-random Sources (Extended Abstract). STOC 1987: 160-168 - [c14]Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani:
Matching Is as Easy as Matrix Inversion. STOC 1987: 345-354 - 1986
- [j3]Miklos Santha, Umesh V. Vazirani:
Generating Quasi-random Sequences from Semi-random Sources. J. Comput. Syst. Sci. 33(1): 75-87 (1986) - [c13]Umesh V. Vazirani, Vijay V. Vazirani:
Sampling a Population with a Semi-Random Source. FSTTCS 1986: 443-452 - 1985
- [c12]Umesh V. Vazirani, Vijay V. Vazirani:
Random Polynomial Time Is Equal to Slightly-random Polynomial Time. FOCS 1985: 417-428 - [c11]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 - [c10]Umesh V. Vazirani, Vijay V. Vazirani:
The Two-Processor Scheduling Problem is in R-NC. STOC 1985: 11-21 - [c9]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 - 1984
- [j2]Christos H. Papadimitriou, Umesh V. Vazirani:
On Two Geometric Problems Related to the Traveling Salesman Problem. J. Algorithms 5(2): 231-246 (1984) - [c8]Umesh V. Vazirani, Vijay V. Vazirani:
Efficient and Secure Pseudo-Random Number Generation. CRYPTO 1984: 193-202 - [c7]Miklos Santha, Umesh V. Vazirani:
Generating Quasi-Random Sequences from Slightly-Random Sources (Extended Abstract). FOCS 1984: 434-440 - [c6]Umesh V. Vazirani, Vijay V. Vazirani:
Efficient and Secure Pseudo-Random Number Generation (Extended Abstract). FOCS 1984: 458-463 - 1983
- [j1]Umesh V. Vazirani, Vijay V. Vazirani:
A Natural Encoding Scheme Proved Probabilistic Polynomial Complete. Theor. Comput. Sci. 24: 291-300 (1983) - [c5]Manuel Blum, Umesh V. Vazirani, Vijay V. Vazirani:
Reducibility Among Protocols. CRYPTO 1983: 137-146 - [c4]Umesh V. Vazirani, Vijay V. Vazirani:
RSA Bits are 732+epsilon Secure. CRYPTO 1983: 369-375 - [c3]Umesh V. Vazirani, Vijay V. Vazirani:
Trapdoor Pseudo-random Number Generators, with Applications to Protocol Design. FOCS 1983: 23-30 - [c2]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 - 1982
- [c1]Umesh V. Vazirani, Vijay V. Vazirani:
A Natural Encoding Scheme Proved Probabilistic Polynomial Complete. FOCS 1982: 40-44
Coauthor Index
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
load content from web.archive.org
Privacy notice: By enabling the option above, your browser will contact the API of web.archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2023-03-26 01:42 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
