Optimal Demand-oriented Topology for Hypertext Systems. - Scott Aaronson (SIGIR, 1997)

Quantum lower bound for the collision problem. - Scott Aaronson (STOC, 2002)

Quantum Lower Bound for Recursive Fourier Sampling - Scott Aaronson (Electron. Colloquium Comput. Complex., 2002)

Book review: On "A New Kind of Science" by Stephen Wolfram. - Scott Aaronson (Quantum Inf. Comput., 2002)

Is P Versus NP Formally Independent? - Scott Aaronson (Bull. EATCS, 2003)

Multilinear Formulas and Skepticism of Quantum Computing - Scott Aaronson (Electron. Colloquium Comput. Complex., 2003)

Algorithms for Boolean Function Query Properties. - Scott Aaronson (SIAM J. Comput., 2003)

Limits on Efficient Computation in the Physical World - Scott Aaronson (CoRR, 2004)

Improved Simulation of Stabilizer Circuits - Scott Aaronson; Daniel Gottesman (CoRR, 2004)

Limitations of Quantum Advice and One-Way Communication - Scott Aaronson (Electron. Colloquium Comput. Complex., 2004)

The Complexity of Agreement - Scott Aaronson (Electron. Colloquium Comput. Complex., 2004)

Quantum lower bounds for the collision and the element distinctness problems. - Scott Aaronson; Yaoyun Shi (J. ACM, 2004)

Quantum Computing, Postselection, and Probabilistic Polynomial-Time - Scott Aaronson (Electron. Colloquium Comput. Complex., 2005)

NP-complete Problems and Physical Reality - Scott Aaronson (Electron. Colloquium Comput. Complex., 2005)

Oracles Are Subtle But Not Malicious - Scott Aaronson (Electron. Colloquium Comput. Complex., 2005)

QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols - Scott Aaronson (Electron. Colloquium Comput. Complex., 2005)

Guest Column: NP-complete problems and physical reality. - Scott Aaronson (SIGACT News, 2005)

Quantum Search of Spatial Regions. - Scott Aaronson; Andris Ambainis (Theory Comput., 2005)

QMA/qpoly subseteq PSPACE/poly: De-Merlinizing Quantum Protocols. - Scott Aaronson (CCC, 2006)

The Learnability of Quantum States. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2006)

Quantum Versus Classical Proofs and Advice. - Scott Aaronson; Greg Kuperberg (Electron. Colloquium Comput. Complex., 2006)

Lower Bounds for Local Search by Quantum Arguments. - Scott Aaronson (SIAM J. Comput., 2006)

The Limits of Quantum Computers. - Scott Aaronson (CSR, 2007)

Review of "The Access Principle by John Willinsky, " MIT Press, 2005. - Scott Aaronson (SIGACT News, 2007)

The Polynomial Method in Quantum and Classical Computing. - Scott Aaronson (FOCS, 2008)

On Perfect Completeness for QMA. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2008)

The Power of Unentanglement. - Scott Aaronson; Salman Beigi; Andrew Drucker; Bill Fefferman; Peter W. Shor (Electron. Colloquium Comput. Complex., 2008)

Algebrization: A New Barrier in Complexity Theory. - Scott Aaronson; Avi Wigderson (Electron. Colloquium Comput. Complex., 2008)

Closed Timelike Curves Make Quantum and Classical Computing Equivalent. - Scott Aaronson; John Watrous (Electron. Colloquium Comput. Complex., 2008)

Quantum certificate complexity. - Scott Aaronson (J. Comput. Syst. Sci., 2008)

Quantum Copy-Protection and Quantum Money. - Scott Aaronson (CCC, 2009)

The One-Way Communication Complexity of Group Membership - Scott Aaronson; François Le Gall; Alexander Russell; Seiichiro Tani (CoRR, 2009)

BQP and the Polynomial Hierarchy. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2009)

The Need for Structure in Quantum Speedups. - Scott Aaronson; Andris Ambainis (Electron. Colloquium Comput. Complex., 2009)

Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006). - Scott Aaronson; Sudipto Guha; Jon M. Kleinberg; Frank McSherry; Dieter van Melkebeek; Amit Sahai (SIAM J. Comput., 2009)

Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol. - Andrew Lutomirski; Scott Aaronson; Edward Farhi; David Gosset; Jonathan A. Kelner; Avinatan Hassidim; Peter W. Shor (ICS, 2010)

QIP = PSPACE breakthrough: technical perspective. - Scott Aaronson (Commun. ACM, 2010)

A Counterexample to the Generalized Linial-Nisan Conjecture. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2010)

The Equivalence of Sampling and Searching. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2010)

The Computational Complexity of Linear Optics. - Scott Aaronson; Alex Arkhipov (Electron. Colloquium Comput. Complex., 2010)

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. - Scott Aaronson; Baris Aydinlioglu; Harry Buhrman; John M. Hitchcock; Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2010)

A note on circuit lower bounds from derandomization. - Scott Aaronson; Dieter van Melkebeek (Electron. Colloquium Comput. Complex., 2010)

The One-Way Communication Complexity of Subgroup Membership. - Scott Aaronson; François Le Gall; Alexander Russell; Seiichiro Tani (Chic. J. Theor. Comput. Sci., 2011)

Impossibility of Succinct Quantum Proofs for Collision-Freeness. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2011)

A Linear-Optical Proof that the Permanent is #P-Hard. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2011)

Why Philosophers Should Care About Computational Complexity. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2011)

Advice Coins for Classical and Quantum Computation. - Scott Aaronson; Andrew Drucker (Electron. Colloquium Comput. Complex., 2011)

Special Section on Foundations of Computer Science. - Scott Aaronson; Jeff Erickson 001; Mohammad Mahdian; R. Ravi 001; Emanuele Viola (SIAM J. Comput., 2011)

On Circuit Lower Bounds from Derandomization. - Scott Aaronson; Dieter van Melkebeek (Theory Comput., 2011)

Quantum money. - Scott Aaronson; Edward Farhi; David Gosset; Avinatan Hassidim; Jonathan A. Kelner; Andrew Lutomirski (Commun. ACM, 2012)

Quantum Money from Hidden Subspaces. - Scott Aaronson; Paul F. Christiano (Electron. Colloquium Comput. Complex., 2012)

Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent. - Scott Aaronson; Travis Hance (Electron. Colloquium Comput. Complex., 2012)

Quantum Computing since Democritus. - Scott Aaronson (Cambridge University Press, 2013)

Sophistication as Randomness Deficiency. - Francisco Mota; Scott Aaronson; Luis Filipe Coelho Antunes; Andre Souto (DCFS, 2013)

The Ghost in the Quantum Turing Machine. - Scott Aaronson (CoRR, 2013)

BosonSampling Is Far From Uniform. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2013)

Weak Parity. - Scott Aaronson; Andris Ambainis; Kaspars Balodis; Mohammad Bavarian (Electron. Colloquium Comput. Complex., 2013)

Any Beamsplitter Generates Universal Quantum Linear Optics. - Adam Bouland; Scott Aaronson (Electron. Colloquium Comput. Complex., 2013)

Quantum POMDPs. - Jennifer Barry; Daniel T. Barry; Scott Aaronson (CoRR, 2014)

The space "just above" BQP. - Scott Aaronson; Adam Bouland; Joseph F. Fitzsimons; Mitchell Lee (Electron. Colloquium Comput. Complex., 2014)

AM with Multiple Merlins. - Scott Aaronson; Russell Impagliazzo; Dana Moshkovitz (Electron. Colloquium Comput. Complex., 2014)

Quantum lower bound for inverting a permutation with advice. - Aran Nayebi; Scott Aaronson; Aleksandrs Belovs; Luca Trevisan 001 (Electron. Colloquium Comput. Complex., 2014)

Bosonsampling is far from uniform. - Scott Aaronson; Alex Arkhipov (Quantum Inf. Comput., 2014)

A Full Characterization of Quantum Advice. - Scott Aaronson; Andrew Drucker (SIAM J. Comput., 2014)

BosonSampling with Lost Photons. - Scott Aaronson; Daniel J. Brod (CoRR, 2015)

Sculpting Quantum Speedups. - Scott Aaronson; Shalev Ben-David (Electron. Colloquium Comput. Complex., 2015)

Separations in query complexity using cheat sheets. - Scott Aaronson; Shalev Ben-David; Robin Kothari (Electron. Colloquium Comput. Complex., 2015)

The Classification of Reversible Bit Operations. - Scott Aaronson; Daniel Grier; Luke Schaeffer (Electron. Colloquium Comput. Complex., 2015)

The Ghost in the Quantum Turing Machine. - Scott Aaronson (The Once and Future Turing, 2016)

P =? NP - Scott Aaronson (Open Problems in Mathematics, 2016)

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. - Scott Aaronson; Andris Ambainis; Janis Iraids; Martins Kokainis; Juris Smotrovs (CCC, 2016)

A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory. - Adam Yedidia; Scott Aaronson (Complex Syst., 2016)

The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2016)

Computability Theory of Closed Timelike Curves. - Scott Aaronson; Mohammad Bavarian; Giulio G. Giusteri (Electron. Colloquium Comput. Complex., 2016)

Complexity-Theoretic Foundations of Quantum Supremacy Experiments. - Scott Aaronson; Lijie Chen 001 (Electron. Colloquium Comput. Complex., 2016)

Doubly infinite separation of quantum information and communication. - Zi-Wen Liu; Christopher Perry; Yechao Zhu; Dax Enshan Koh; Scott Aaronson (Electron. Colloquium Comput. Complex., 2016)

The computational complexity of ball permutations. - Scott Aaronson; Adam Bouland; Greg Kuperberg; Saeed Mehraban (STOC, 2017)

On the implausibility of classical client blind quantum computing. - Scott Aaronson; Alexandru Cojocaru; Alexandru Gheorghiu; Elham Kashefi (CoRR, 2017)

Experimental learning of quantum states. - Andrea Rocchetto; Scott Aaronson; Simone Severini; Gonzalo Carvacho; Davide Poderini; Iris Agresti; Marco Bentivegna; Fabio Sciarrino (CoRR, 2017)

P=?NP. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2017)

Online Learning of Quantum States. - Scott Aaronson; Xinyi Chen 001; Elad Hazan; Satyen Kale; Ashwin Nayak 001 (NeurIPS, 2018)

Online Learning of Quantum States. - Scott Aaronson; Xinyi Chen 001; Elad Hazan; Ashwin Nayak 001 (CoRR, 2018)

PDQP/qpoly = ALL. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2018)

Quantum Lower Bound for Approximate Counting Via Laurent Polynomials. - Scott Aaronson (Electron. Colloquium Comput. Complex., 2018)

Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. - Scott Aaronson; Andris Ambainis (SIAM J. Comput., 2018)

The fewest clues problem. - Erik D. Demaine; Fermi Ma; Ariel Schvartzman; Erik Waingarten; Scott Aaronson (Theor. Comput. Sci., 2018)

Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. - Scott Aaronson; Alexandru Cojocaru; Alexandru Gheorghiu; Elham Kashefi (ICALP, 2019)

A Quantum Query Complexity Trichotomy for Regular Languages. - Scott Aaronson; Daniel Grier; Luke Schaeffer (Electron. Colloquium Comput. Complex., 2019)

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. - Scott Aaronson; Robin Kothari; William Kretschmer; Justin Thaler (Electron. Colloquium Comput. Complex., 2019)

Gentle Measurement of Quantum States and Differential Privacy. - Scott Aaronson; Guy N. Rothblum (Electron. Colloquium Comput. Complex., 2019)

On the Quantum Complexity of Closest Pair and Related Problems. - Scott Aaronson; Nai-Hui Chia; Han-Hsuan Lin; Chunhao Wang; Ruizhe Zhang 001 (CCC, 2020)

Quantum Approximate Counting, Simplified. - Scott Aaronson; Patrick Rall (SOSA, 2020)

Quantum Copy-Protection from Hidden Subspaces. - Scott Aaronson; Jiahui Liu 003; Ruizhe Zhang 001 (CoRR, 2020)

On the Hardness of Detecting Macroscopic Superpositions. - Scott Aaronson; Yosi Atia; Leonard Susskind (Electron. Colloquium Comput. Complex., 2020)

Quantum Implications of Huang's Sensitivity Theorem. - Scott Aaronson; Shalev Ben-David; Robin Kothari; Avishay Tal (Electron. Colloquium Comput. Complex., 2020)

New Approaches for Quantum Copy-Protection. - Scott Aaronson; Jiahui Liu 003; Qipeng Liu 001; Mark Zhandry; Ruizhe Zhang 001 (IACR Cryptol. ePrint Arch., 2020)

Shadow Tomography of Quantum States. - Scott Aaronson (SIAM J. Comput., 2020)

The Busy Beaver Frontier. - Scott Aaronson (SIGACT News, 2020)

On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking. - Scott Aaronson; Sam Gunn (Theory Comput., 2020)

BQP After 28 Years (Invited Talk). - Scott Aaronson (FSTTCS, 2021)

Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. - Scott Aaronson; Shalev Ben-David; Robin Kothari; Shravas Rao; Avishay Tal (STOC, 2021)

Efficient Learning of Non-Interacting Fermion Distributions. - Scott Aaronson; Sabee Grewal (CoRR, 2021)

Open Problems Related to Quantum Query Complexity. - Scott Aaronson (CoRR, 2021)

On quantum versus classical query complexity. - Scott Aaronson; Andris Ambainis; Andrej Bogdanov; Krishnamoorthy Dinesh 001; Tsun Ming Cheung (Electron. Colloquium Comput. Complex., 2021)

The Acrobatics of BQP. - Scott Aaronson; DeVon Ingram; William Kretschmer (Electron. Colloquium Comput. Complex., 2021)

A very preliminary analysis of DALL-E 2. - Gary Marcus 001; Ernest Davis; Scott Aaronson (CoRR, 2022)

How Much Structure Is Needed for Huge Quantum Speedups? - Scott Aaronson (CoRR, 2022)

Discrete Bulk Reconstruction. - Scott Aaronson; Jason Pollack (CoRR, 2022)

Learning Distributions over Quantum Measurement Outcomes. - Weiyuan Gong; Scott Aaronson (ICML, 2023)

Efficient Tomography of Non-Interacting-Fermion States. - Scott Aaronson; Sabee Grewal (TQC, 2023)

Testing GPT-4 with Wolfram Alpha and Code Interpreter plug-ins on math and science problems. - Ernest Davis; Scott Aaronson (CoRR, 2023)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. - Scott Aaronson; Harry Buhrman; William Kretschmer (Electron. Colloquium Comput. Complex., 2023)

Certified Randomness from Quantum Supremacy. - Scott Aaronson; Shih-Han Hung (Electron. Colloquium Comput. Complex., 2023)

An Automated Approach to the Collatz Conjecture. - Emre Yolcu; Scott Aaronson; Marijn J. H. Heule (J. Autom. Reason., 2023)

Quantum Pseudoentanglement. - Scott Aaronson; Adam Bouland; Bill Fefferman; Soumik Ghosh; Umesh V. Vazirani; Chenyi Zhang 003; Zixin Zhou (ITCS, 2024)

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements. - Scott Aaronson; Sabee Grewal; Vishnu Iyer; Simon C. Marshall; Ronak Ramachandran (CoRR, 2024)

Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks. - Simon C. Marshall; Scott Aaronson; Vedran Dunjko (CCC, 2025)

Certified randomness using a trapped-ion quantum processor. - Minzhao Liu; Ruslan Shaydulin; Pradeep Niroula; Matthew DeCross; Shih-Han Hung; Wen Yu Kon; Enrique Cervero Martín; Kaushik Chakraborty; Omar Amer; Scott Aaronson; Atithi Acharya; Yuri Alexeev; et al. (Nat., 2025)