Research Papers and Surveys

(Mostly-)Quantum Papers

S. Aaronson and L. Chen. Complexity-Theoretic Foundations of Quantum Supremacy Experiments [PDF], 2016. ECCC TR16-200, arXiv:1612.05903.

S. Aaronson, A. Bouland, G. Kuperberg, and S. Mehraban. The Computational Complexity of Ball Permutations, 2016. arXiv:1610.06646.

S. Aaronson, M. Bavarian, and G. Gueltrini. Computability Theory of Closed Timelike Curves [PDF], 2016. ECCC TR16-146.

S. Aaronson and S. Ben-David. Sculpting Quantum Speedups, in Proceedings of CCC'2016. ECCC TR15-203, arXiv:1512.04016.

S. Aaronson, A. Ambainis, J. Iraids, M. Kokainis, and J. Smotrovs. Polynomials, Quantum Query Complexity, and Grothendieck's Inequality, in Proceedings of CCC'2016. arXiv:1511.08682.

S. Aaronson, S. Ben-David, and R. Kothari. Separations in Query Complexity Using Cheat Sheets, in Proceedings of ACM STOC'2016. ECCC TR15-175, arXiv:1511.01937.

S. Aaronson and D. J. Brod. BosonSampling with Lost Photons, Phys. Rev. A 93:012335, 2016. arXiv:1510.05245.

Z. Liu, C. Perry, Y. Zhu, D. Koh, and S. Aaronson. Doubly Infinite Separation of Quantum Information and Communication, Phys. Rev. A 93:012347, 2016. arXiv:1507.03546.

S. Aaronson and A. Ambainis. Forrelation: A Problem that Optimally Separates Quantum from Classical Computing [PDF], in Proceedings of ACM STOC'2015, pp. 307-316. Conference version [PDF]. arXiv:1411.5729, ECCC TR14-155.

S. Aaronson, A. Bouland, J. Fitzsimons, and M. Lee. The Space "Just Above" BQP, in Proceedings of ACM ITCS (Innovations in Theoretical Computer Science) 2016, pp. 271-280. arXiv:1412.6507, ECCC TR14-181.

R. Gross and S. Aaronson. Bounding the Seed Length of Miller and Shi's Unbounded Randomness Expansion Protocol, 2014. arXiv:1410.8019.

A. Nayebi, S. Aaronson, A. Belovs, and L. Trevisan. Quantum Lower Bound for Inverting a Permutation with Advice, to appear in Quantum Information and Computation 15(11-12):901-913, 2015. ECCC TR14-109, arXiv:1408.3193.

J. Barry, D. Barry, and S. Aaronson. Quantum POMDPs Physical Review A 90:032311, 2014. arXiv:1406.2858.

A. Bouland and S. Aaronson. Any Beamsplitter Generates Universal Quantum Linear Optics [PDF], Physical Review A 89:062316, 2014. arXiv:1310.6718, ECCC TR13-147.

S. Aaronson and A. Arkhipov. BosonSampling Is Far From Uniform [PS] [PDF], Quantum Information and Computation, vol. 14, no. 15&16, pp. 1383--1423, 2014. arXiv:1309.7460, ECCC TR13-135.

S. Aaronson, A. Bouland, L. Chua, and G. Lowther. Psi-Epistemic Theories: The Role of Symmetry [PS] [PDF], Physical Review A 88:032111, 2013. arXiv:1303.2834.

M. A. Broome, A. Fedrizzi, S. Rahimi-Keshari, J. Dove, S. Aaronson, T. Ralph, and A. G. White. Photonic Boson Sampling in a Tunable Circuit, Science 339(6121):794-798, February 2013. arXiv:1212.2234.

S. Aaronson and P. Christiano. Quantum Money from Hidden Subspaces [PS] [PDF], Theory of Computing 9(9):349-401, 2013. Conference version [PS] [PDF] in Proceedings of ACM STOC 2012, pages 41-60. arXiv:1203.4740, ECCC TR12-024.

S. Aaronson. A Linear-Optical Proof that the Permanent is #P-Hard [PS] [PDF], Proceedings of the Royal Society A, 467:3393-3405, 2011. ECCC TR11-043, arXiv:1109.1674.

S. Aaronson. Impossibility of Succinct Quantum Proofs for Collision-Freeness [PS] [PDF], Quantum Information and Computation, 12:21-28, 2012. ECCC TR11-001, arXiv:1101.0403.

S. Aaronson and A. Drucker. Advice Coins for Classical and Quantum Computation [PS] [PDF], in Proceedings of ICALP 2011, pages 61-72. ECCC TR11-008, arXiv:1101.5355.

S. Aaronson and A. Arkhipov. The Computational Complexity of Linear Optics [PDF], Theory of Computing 4:143-252, 2013. Conference version [PS] [PDF] in Proceedings of ACM STOC 2011, pages 333-342. ECCC TR10-170, arXiv:1011.3245. See also BosonSampling Mathematica notebook by Justin Dove.

S. Aaronson and A. Drucker. A Full Characterization of Quantum Advice [PDF], SIAM Journal on Computing 43(3):1131-1183, 2014. Conference version [PS] [PDF] in Proceedings of ACM STOC 2010, pages 131-140. ECCC TR10-057, arXiv:1004.0377.

A. Lutomirski, S. Aaronson, E. Farhi, D. Gosset, A. Hassidim, J. Kelner, and P. Shor. Breaking and making quantum money: toward a new quantum cryptographic protocol, Proceedings of Innovations in Computer Science (ICS), 2010. arXiv:0912.3825.

S. Aaronson and A. Ambainis. The Need for Structure in Quantum Speedups [PS] [PDF], in Proceedings of ICS 2011, pages 338-352. arXiv:0911.0996, ECCC TR09-110.

S. Aaronson. BQP and the Polynomial Hierarchy [PS] [PDF], in Proceedings of ACM STOC 2010, pages 141-150. arXiv:0910.4698, ECCC TR09-104.

S. Aaronson. Quantum Copy-Protection and Quantum Money [PS] [PDF], conference version in Proceedings of IEEE Complexity 2009, pages 229-242.

S. Aaronson, F. Le Gall, A. Russell, and S. Tani. The One-Way Communication Complexity of Group Membership [PS] [PDF], Chicago Journal of Theoretical Computer Science Article 6, 2011. arXiv:0902.3175.

S. Aaronson and J. Watrous. Closed Timelike Curves Make Quantum and Classical Computing Equivalent [PS] [PDF], Proceedings of the Royal Society A 465:631-647, 2009. arXiv:0808.2669.

S. Aaronson. On Perfect Completeness for QMA [PS] [PDF], Quantum Information & Computation, vol. 9, pp. 81-89, 2009. arXiv:0806.0450.

N. Harrigan, T. Rudolph, and S. Aaronson. Representing Probabilistic Data via Ontological Models, 2008. arXiv:0709.1149.

S. Aaronson, S. Beigi, A. Drucker, B. Fefferman and P. Shor. The Power of Unentanglement [PS] [PDF], Theory of Computing, 5(1):1-42, 2009. Conference version [PS] [PDF] in Proceedings of IEEE Complexity 2008, pp. 223-236. arXiv:0804.0802.

S. Aaronson. The Learnability of Quantum States [PS] [PDF], Proceedings of the Royal Society A463(2088), 2007. quant-ph/0608142.

S. Aaronson and G. Kuperberg. Quantum Versus Classical Proofs and Advice [PS] [PDF], Theory of Computing 3(7):129-157, 2007. Conference version [PS] [PDF] in Proceedings of IEEE Complexity 2007, pp. 115-128. quant-ph/0604056.

S. Aaronson. QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols [PS] [PDF], in Proceedings of IEEE Complexity 2006, pages 261-273. quant-ph/0510230.

S. Aaronson. Quantum Computing, Postselection, and Probabilistic Polynomial-Time [PS] [PDF], Proceedings of the Royal Society A, 461(2063):3473-3482, 2005. quant-ph/0412187.

S. Aaronson. Quantum Computing and Hidden Variables [PS] [PDF], Physical Review A 71:032325, March 2005. quant-ph/0408035 and quant-ph/0408119.

S. Aaronson and D. Gottesman. Improved Simulation of Stabilizer Circuits [PS] [PDF] [Webpage], Physical Review A 70:052328, 2004. quant-ph/0406196.

S. Aaronson. Limitations of Quantum Advice and One-Way Communication [PS] [PDF], Theory of Computing 1:1-28, 2005. Conference version in Proceedings of IEEE Complexity 2004 pp. 320-332 (won the Ron Book Best Student Paper Award). quant-ph/0402095.

S. Aaronson. Is Quantum Mechanics An Island In Theoryspace? [PS] [PDF], Proceedings of the Växjö Conference "Quantum Theory: Reconsideration of Foundations" (A. Khrennikov, ed.), 2004. quant-ph/0401062.

S. Aaronson. Multilinear Formulas and Skepticism of Quantum Computing [PS] [PDF], in STOC 2004, pp. 118-127. Conference version [PS] [PDF]. quant-ph/0311039.

S. Aaronson. Lower Bounds for Local Search by Quantum Arguments [PS] [PDF], Proceedings of ACM STOC 2004, pp. 465-474 (won the Danny Lewin Best Student Paper Award). Also in STOC'04 Special Issue of SIAM Journal on Computing. quant-ph/0307149.

S. Aaronson and A. Ambainis. Quantum Search of Spatial Regions [PS] [PDF], Theory of Computing 1:47-79, 2005. Conference version [PS] [PDF] in Proceedings of IEEE FOCS 2003, pp. 200-209. quant-ph/0303041.

S. Aaronson. Quantum Certificate Complexity [PS] [PDF], IEEE Conference on Computational Complexity (CCC) 2003, pp. 171-178 (won the Ron Book Best Student Paper Award). Journal version [PS] [PDF] in JCSS Special Issue for Complexity 2003. ECCC TR03-005, quant-ph/0210020.

S. Aaronson. Quantum Lower Bound for Recursive Fourier Sampling [PS] [PDF], Quantum Information and Computation 3(2):165-174, 2003. quant-ph/0209060.

S. Aaronson. Quantum Lower Bound for the Collision Problem [PS] [PDF], Proceedings of ACM STOC 2002, pp. 635-642 (won the C. V. Ramamoorthy Award). Journal version (joint with Y. Shi) in Journal of the ACM 51(4):595-605, 2004. quant-ph/0111102.

(Mostly-)Classical Papers

N. Roquet, A. P. Soleimany, A. C. Ferris, S. Aaronson, and T. K. Lu. Synthetic Recombinase-Based State Machines in Living Cells [click here] [blog post], Science 353(6297), July 22, 2016.

E. Demaine, F. Ma, A. Schvartzman, E. Waingarten, and S. Aaronson. The Fewest Clues Problem [PDF], in Proceedings of FUN'2016.

A. Yedidia and S. Aaronson. A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory [PDF], Complex Systems 25(4), 2016.

S. Aaronson, D. Grier, and L. Schaefer. The Classification of Reversible Bit Operations [PDF], in Proceedings of Innovations in Theoretical Computer Science (ITCS), 2017. ECCC TR15-066, arXiv:1504.05155.

S. Aaronson and H. Nguyen. Near Invariance of the Hypercube [PS] [PDF], Israel Journal of Mathematics 212(1):385--417, 2016. arXiv:1409.7447.

S. Aaronson, S. M. Carroll, and L. Ouellette. Quantifying the Rise and Fall of Complexity in Closed Systems: The Coffee Automaton [PDF], 2014.

S. Aaronson, R. Impagliazzo, and D. Moshkovitz. AM with Multiple Merlins [PDF], in Proceedings of Conference on Computational Complexity (CCC), 2014. ECCC TR14-012, arXiv:1401.6848.

S. Aaronson, A. Ambainis, K. Balodis, and M. Bavarian. Weak Parity [PDF], in Proceedings of International Colloquium on Automata, Languages, and Programming (ICALP), 2014. ECCC TR13-164, arXiv:1312.0036.

S. Aaronson and T. Hance. Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent [PS] [PDF], Quantum Information and Computation, 14(7-8):541-559, 2014. ECCC TR12-170.

F. Mota, S. Aaronson, L. Antunes, and A. Souto. Sophistication as Randomness Deficiency [PDF], Descriptional Complexity of Formal Systems, Lecture Notes in Computer Science Volume 8031, pp. 172-181, 2013.

S. Aaronson, B. Aydinlioglu, H. Buhrman, J. Hitchcock, and D. van Melkebeek. A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games, 2010. ECCC TR10-174.

S. Aaronson. The Equivalence of Sampling and Searching [PS] [PDF], in Proceedings of International Computer Science Symposium in Russia (CSR), pp. 1-14, 2011 (won the Best Paper Award). Journal version in Theory of Computing Systems, 2014. arXiv:1009.5104, ECCC TR10-128.

S. Aaronson and D. van Melkebeek. On Circuit Lower Bounds from Derandomization, Theory of Computing 7(1):177-184, 2011. ECCC TR10-105.

S. Aaronson. A Counterexample to the Generalized Linial-Nisan Conjecture [PS] [PDF], 2010. ECCC TR10-109.

S. Aaronson and A. Wigderson. Algebrization: A New Barrier in Complexity Theory [PS] [PDF], ACM Transactions on Computing Theory 1(1), 2009. Conference version [PS] [PDF] in Proceedings of ACM STOC'2008, pp. 731-740.

S. Aaronson. Oracles Are Subtle But Not Malicious [PS] [PDF], in Proceedings of IEEE Complexity 2006, pages 340-354. cs.CC/0504048.

S. Aaronson. The Complexity of Agreement [PS] [PDF]. Conference version [PS] [PDF] in Proceedings of ACM STOC 2005, pp. 634-643. cs.CC/0406061.

S. Aaronson. Algorithms for Boolean Function Query Properties [PS] [PDF], SIAM Journal on Computing 32(5):1140-1157, 2003.

S. Aaronson. Stylometric Clustering: A Comparison of Data-Driven and Syntactic Features [MS Word], 2001.

S. Aaronson. Optimal Demand-Oriented Topology for Hypertext Systems [PS] [PDF], in Proceedings of ACM SIGIR 1997, pp. 168-177.

Surveys and Book Reviews

S. Aaronson. P=?NP [PDF], in Open Problems in Mathematics (Springer), 2016. ECCC TR17-004.

S. Aaronson (with A. Bouland and L. Schaeffer). The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes [PDF], Barbados Lecture Notes, 2016. ECCC TR16-109.

S. Aaronson. Quantum Machine Learning Algorithms: Read the Fine Print [PDF], Nature Physics 11:291-293, 2015.

S. Aaronson. The Ghost in the Quantum Turing Machine [PDF] [PS], in The Once and Future Turing, edited by S. Barry Cooper and Andrew Hodges, 2016.

S. Aaronson. Get Real [PDF] [HTML], Nature Physics News & Views, 8:443–444, 2012.

S. Aaronson. Why Philosophers Should Care About Computational Complexity [PS] [PDF], pp. 261-328 in Computability: Turing, Gödel, Church, and Beyond, edited by B. J. Copeland, C. Posy, and O. Shagrir, MIT Press, 2013. ECCC TR11-108, arXiv:1108.1791.

S. Aaronson. QIP = PSPACE Breakthrough (Technical Perspective) [HTML] [PDF], Communications of the ACM, 53(12):101, December 2010.

S. Aaronson. Why Quantum Chemistry Is Hard [HTML] [PS] [PDF], Nature Physics News & Views, 5(10):707-708, 2009.

S. Aaronson. Are Quantum States Exponentially Long Vectors? [PS] [PDF], shorter version in Proceedings of the 2005 Oberwolfach Meeting on Complexity Theory. quant-ph/0507242.

S. Aaronson. NP-complete Problems and Physical Reality [PS] [PDF], SIGACT News Complexity Theory Column, March 2005. quant-ph/0502072.

S. Aaronson. Is P Versus NP Formally Independent? [PS] [PDF], Bulletin of the EATCS 81, October 2003.

S. Aaronson. Book Review: A New Kind of Science [PS] [PDF], Quantum Information and Computation 2(5):410-423, 2002. quant-ph/0206089.

[Return to home page]