Research Papers and Surveys


(Mostly-)Quantum Papers


A. Nayebi, S. Aaronson, A. Belovs, and L. Trevisan. Quantum Lower Bound for Inverting a Permutation with Advice, 2014. ECCC TR14-109, arXiv:1408.3193.


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


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


S. Aaronson and A. Arkhipov. BosonSampling Is Far From Uniform [PS] [PDF], to appear in Quantum Information and Computation, 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 Vxj 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


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 to appear 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. The Ghost in the Quantum Turing Machine [PDF] [PS], to appear in The Once and Future Turing, edited by S. Barry Cooper and Andrew Hodges, 2014.


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


S. Aaronson. Why Philosophers Should Care About Computational Complexity [PS] [PDF], pp. 261-328 in Computability: Turing, Gdel, 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]