Scott J. Aaronson, Ph.D. - Publications

Affiliations: 
2004 University of California, Berkeley, Berkeley, CA, United States 
Area:
Security (SEC); Theory (THY), Complexity theory

38 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
2020 Aaronson S. Shadow Tomography of Quantum States Siam Journal On Computing. DOI: 10.1137/18M120275X  0.442
2019 Rocchetto A, Aaronson S, Severini S, Carvacho G, Poderini D, Agresti I, Bentivegna M, Sciarrino F. Experimental learning of quantum states Science Advances. 5. PMID 30944851 DOI: 10.1126/Sciadv.Aau1946  0.442
2019 Aaronson S, Chen X, Hazan E, Kale S, Nayak A. Online learning of quantum states Journal of Statistical Mechanics: Theory and Experiment. 2019: 124019. DOI: 10.1088/1742-5468/Ab3988  0.366
2018 Demaine ED, Ma F, Schvartzman A, Waingarten E, Aaronson S. The fewest clues problem Theoretical Computer Science. 748: 28-39. DOI: 10.1016/J.Tcs.2018.01.020  0.33
2017 Aaronson S, Chen L. Complexity-theoretic foundations of quantum supremacy experiments Electronic Colloquium On Computational Complexity. 23: 67. DOI: 10.4230/Lipics.Ccc.2017.22  0.519
2016 Liu ZW, Perry C, Zhu Y, Koh DE, Aaronson S. Doubly infinite separation of quantum information and communication Physical Review a - Atomic, Molecular, and Optical Physics. 93. DOI: 10.1103/Physreva.93.012347  0.448
2016 Aaronson S, Brod DJ. BosonSampling with lost photons Physical Review a - Atomic, Molecular, and Optical Physics. 93. DOI: 10.1103/Physreva.93.012335  0.411
2016 Aaronson S, Nguyen H. Near invariance of the hypercube Israel Journal of Mathematics. 212: 385-417. DOI: 10.1007/S11856-016-1291-Z  0.366
2015 Aaronson S, Ambainis A. Forrelation: A problem that optimally separates quantum from classical computing Proceedings of the Annual Acm Symposium On Theory of Computing. 14: 307-316. DOI: 10.1137/15M1050902  0.648
2015 Aaronson S. Read the fine print Nature Physics. 11: 291-293. DOI: 10.1038/Nphys3272  0.353
2014 Aaronson S, Ambainis A. Theory of Computing. 10: 133-166. DOI: 10.4086/Toc.2014.V010A006  0.637
2014 Aaronson S, Drucker A. A full characterization of quantum advice Siam Journal On Computing. 43: 1131-1183. DOI: 10.1137/110856939  0.487
2014 Barry J, Barry DT, Aaronson S. Quantum partially observable Markov decision processes Physical Review A. 90: 32311. DOI: 10.1103/Physreva.90.032311  0.387
2014 Aaronson S. The Equivalence of Sampling and Searching Theory of Computing Systems \/ Mathematical Systems Theory. 55: 281-298. DOI: 10.1007/S00224-013-9527-3  0.379
2013 Broome MA, Fedrizzi A, Rahimi-Keshari S, Dove J, Aaronson S, Ralph TC, White AG. Photonic boson sampling in a tunable circuit. Science (New York, N.Y.). 339: 794-8. PMID 23258411 DOI: 10.1126/Science.1231440  0.401
2013 Aaronson S, Christiano P. Quantum Money from Hidden Subspaces Theory of Computing. 9: 349-401. DOI: 10.4086/Toc.2013.V009A009  0.47
2013 Aaronson S, Bouland A, Chua L, Lowther G. ψ-epistemic theories: The role of symmetry Physical Review A. 88. DOI: 10.1103/Physreva.88.032111  0.353
2012 Aaronson S, Farhi E, Gosset D, Hassidim A, Kelner J, Lutomirski A. Quantum money Communications of the Acm. 55: 84-92. DOI: 10.1145/2240236.2240258  0.353
2012 Aaronson S. Quantum mechanics: Get real Nature Physics. 8: 443-444. DOI: 10.1038/Nphys2325  0.469
2011 Aaronson S, Erickson J, Mahdian M, Ravi R, Viola E. Special Section on Foundations of Computer Science Siam Journal On Computing. 40: 770-770. DOI: 10.1137/Smjcat000040000003000770000001  0.308
2011 Aaronson S. A linear-optical proof that the permanent is #P-hard Proceedings of the Royal Society a: Mathematical, Physical and Engineering Sciences. 467: 3393-3405. DOI: 10.1098/Rspa.2011.0232  0.384
2010 Aaronson S. QIP = PSPACE breakthrough Communications of the Acm. 53: 101. DOI: 10.1145/1859204.1859230  0.425
2009 Aaronson S, Gall FL, Russell A, Tani S. The One-Way Communication Complexity of Subgroup Membership Chicago Journal of Theoretical Computer Science. 2011. DOI: 10.4086/Cjtcs.2011.006  0.302
2009 Aaronson S, Wigderson A. Algebrization: A new barrier in complexity theory Acm Transactions On Computation Theory. 1. DOI: 10.1145/1490270.1490272  0.322
2009 Aaronson S, Guha S, Kleinberg J, McSherry F, van Melkebeek D, Sahai A. Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006) Siam Journal On Computing. 39: vii-vii. DOI: 10.1137/Smjcat000039000001000Vii000001  0.349
2009 Aaronson S, Watrous J. Closed timelike curves make quantum and classical computing equivalent Proceedings of the Royal Society a: Mathematical, Physical and Engineering Sciences. 465: 631-647. DOI: 10.1098/Rspa.2008.0350  0.519
2009 Aaronson S. Computational complexity: Why quantum chemistry is hard Nature Physics. 5: 707-708. DOI: 10.1038/Nphys1415  0.467
2008 Aaronson S. The limits of quantum computers. Scientific American. 298: 50-7. PMID 18357822  0.386
2008 Aaronson S. The limits of quantum computers. Scientific American. 298: 62-69. DOI: 10.1038/Scientificamerican0308-62  0.49
2007 Aaronson S, Kuperberg G. Quantum Versus Classical Proofs and Advice. Theory of Computing. 3: 129-157. DOI: 10.4086/Toc.2007.V003A007  0.48
2007 Aaronson S. The learnability of quantum states Proceedings of the Royal Society a: Mathematical, Physical and Engineering Sciences. 463: 3089-3114. DOI: 10.1098/Rspa.2007.0113  0.495
2006 Aaronson S. Lower bounds for local search by quantum arguments Siam Journal On Computing. 35: 804-824. DOI: 10.1137/S0097539704447237  0.492
2005 Aaronson S. Guest Column: NP-complete problems and physical reality Sigact News. 36: 30-52. DOI: 10.1145/1052796.1052804  0.48
2005 Aaronson S. Quantum computing and hidden variables Physical Review a - Atomic, Molecular, and Optical Physics. 71. DOI: 10.1103/Physreva.71.032325  0.488
2005 Aaronson S. Quantum computing, postselection, and probabilistic polynomial-time Proceedings of the Royal Society a: Mathematical, Physical and Engineering Sciences. 461: 3473-3482. DOI: 10.1098/Rspa.2005.1546  0.509
2004 Aaronson S, Shi Y. Quantum lower bounds for the collision and the element distinctness problems Journal of the Acm. 51: 595-605. DOI: 10.1145/1008731.1008735  0.431
2003 Aaronson S, Ambainis A. Quantum search of spatial regions Annual Symposium On Foundations of Computer Science - Proceedings. 200-209. DOI: 10.4086/Toc.2005.V001A004  0.618
2003 Aaronson S. Algorithms for Boolean function query properties Siam Journal On Computing. 32: 1140-1157. DOI: 10.1137/S0097539700379644  0.361
Show low-probability matches.