Scott Aaronson

According to our database, Scott Aaronson authored at least 119 papers between 1997 and 2025.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2025

Wide Neural Networks as a Baseline for the Computational No-Coincidence Conjecture.

John Dunbar, Scott Aaronson

CoRR, October, 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, K. Jordan Berg, Shouvanik Chakrabarti, Florian J. Curchod, Joan M. Dreiling, Neal Erickson, Cameron Foltz, Michael Foss-Feig, David Hayes, Travis S. Humble, Niraj Kumar, Jeffrey Larson, Danylo Lykov, Michael Mills, Steven A. Moses, Brian Neyenhuis, Shaltiel Eloul, Peter Siegfried, James Walker, Charles Lim, Marco Pistoia

Nat., April, 2025

Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks.

Simon C. Marshall, Scott Aaronson, Vedran Dunjko

Proceedings of the 40th Computational Complexity Conference, 2025

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

A Qubit, a Coin, and an Advice String Walk into a Relational Problem.

Scott Aaronson, Harry Buhrman, William Kretschmer

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Quantum Pseudoentanglement.

Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

Testing GPT-4 with Wolfram Alpha and Code Interpreter plug-ins on math and science problems.

Ernest Davis, Scott Aaronson

CoRR, 2023

Efficient Tomography of Non-Interacting-Fermion States.

Scott Aaronson, Sabee Grewal

Proceedings of the 18th Conference on the Theory of Quantum Computation, 2023

Certified Randomness from Quantum Supremacy.

Scott Aaronson, Shih-Han Hung

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

Learning Distributions over Quantum Measurement Outcomes.

Weiyuan Gong, Scott Aaronson

Proceedings of the International Conference on Machine Learning, 2023

2022

Discrete Bulk Reconstruction.

Scott Aaronson, Jason Pollack

CoRR, 2022

How Much Structure Is Needed for Huge Quantum Speedups?

Scott Aaronson

CoRR, 2022

A very preliminary analysis of DALL-E 2.

Gary Marcus, Ernest Davis, Scott Aaronson

CoRR, 2022

The Acrobatics of BQP.

Scott Aaronson, DeVon Ingram, William Kretschmer

Proceedings of the 37th Computational Complexity Conference, 2022

2021

On quantum versus classical query complexity.

Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsun Ming Cheung

Electron. Colloquium Comput. Complex., 2021

Open Problems Related to Quantum Query Complexity.

Scott Aaronson

CoRR, 2021

Efficient Learning of Non-Interacting Fermion Distributions.

Scott Aaronson, Sabee Grewal

CoRR, 2021

Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem.

Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

BQP After 28 Years (Invited Talk).

Scott Aaronson

Proceedings of the 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2021

New Approaches for Quantum Copy-Protection.

Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang

Proceedings of the Advances in Cryptology - CRYPTO 2021, 2021

An Automated Approach to the Collatz Conjecture.

Emre Yolcu, Scott Aaronson, Marijn J. H. Heule

Proceedings of the Automated Deduction - CADE 28, 2021

2020

On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking.

Scott Aaronson, Sam Gunn

Theory Comput., 2020

The Busy Beaver Frontier.

Scott Aaronson

SIGACT News, 2020

Quantum Implications of Huang's Sensitivity Theorem.

Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal

Electron. Colloquium Comput. Complex., 2020

On the Hardness of Detecting Macroscopic Superpositions.

Scott Aaronson, Yosi Atia, Leonard Susskind

Electron. Colloquium Comput. Complex., 2020

Quantum Copy-Protection from Hidden Subspaces.

Scott Aaronson, Jiahui Liu, Ruizhe Zhang

CoRR, 2020

Quantum Approximate Counting, Simplified.

Scott Aaronson, Patrick Rall

Proceedings of the 3rd Symposium on Simplicity in Algorithms, 2020

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.

Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler

Proceedings of the 35th Computational Complexity Conference, 2020

On the Quantum Complexity of Closest Pair and Related Problems.

Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Gentle measurement of quantum states and differential privacy.

Scott Aaronson, Guy N. Rothblum

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Complexity-Theoretic Limitations on Blind Delegated Quantum Computation.

Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

A Quantum Query Complexity Trichotomy for Regular Languages.

Scott Aaronson, Daniel Grier, Luke Schaeffer

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

PDQP/qpoly=ALL.

Scott Aaronson

Quantum Inf. Comput., 2018

Quantum Lower Bound for Approximate Counting Via Laurent Polynomials.

Scott Aaronson

Electron. Colloquium Comput. Complex., 2018

Online Learning of Quantum States.

Scott Aaronson, Xinyi Chen, Elad Hazan, Ashwin Nayak

CoRR, 2018

Shadow tomography of quantum states.

Scott Aaronson

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Online Learning of Quantum States.

Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, Ashwin Nayak

Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018

2017

P=?NP.

Scott Aaronson

Electron. Colloquium Comput. Complex., 2017

Experimental learning of quantum states.

Andrea Rocchetto, Scott Aaronson, Simone Severini, Gonzalo Carvacho, Davide Poderini, Iris Agresti, Marco Bentivegna, Fabio Sciarrino

CoRR, 2017

On the implausibility of classical client blind quantum computing.

Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi

CoRR, 2017

The computational complexity of ball permutations.

Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

The Classification of Reversible Bit Operations.

Scott Aaronson, Daniel Grier, Luke Schaeffer

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

Complexity-Theoretic Foundations of Quantum Supremacy Experiments.

Scott Aaronson, Lijie Chen

Proceedings of the 32nd Computational Complexity Conference, 2017

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

Computability Theory of Closed Timelike Curves.

Scott Aaronson, Mohammad Bavarian, Giulio G. Giusteri

Electron. Colloquium Comput. Complex., 2016

The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes.

Scott Aaronson

Electron. Colloquium Comput. Complex., 2016

A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory.

Adam Yedidia, Scott Aaronson

Complex Syst., 2016

Separations in query complexity using cheat sheets.

Scott Aaronson, Shalev Ben-David, Robin Kothari

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

The Space "Just Above" BQP.

Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee

Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016

The Fewest Clues Problem.

Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson

Proceedings of the 8th International Conference on Fun with Algorithms, 2016

Sculpting Quantum Speedups.

Scott Aaronson, Shalev Ben-David

Proceedings of the 31st Conference on Computational Complexity, 2016

Polynomials, Quantum Query Complexity, and Grothendieck's Inequality.

Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs

Proceedings of the 31st Conference on Computational Complexity, 2016

P =? NP

Scott Aaronson

Proceedings of the Open Problems in Mathematics., 2016

The Ghost in the Quantum Turing Machine.

Scott Aaronson

Proceedings of the Once and Future Turing: Computing the World, 2016

2015

Quantum lower bound for inverting a permutation with advice.

Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan

Quantum Inf. Comput., 2015

BosonSampling with Lost Photons.

Scott Aaronson, Daniel J. Brod

CoRR, 2015

Forrelation: A Problem that Optimally Separates Quantum from Classical Computing.

Scott Aaronson, Andris Ambainis

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

2014

Generalizing and derandomizing Gurvits's approximation algorithm for the permanent.

Scott Aaronson, Travis Hance

Quantum Inf. Comput., 2014

Bosonsampling is far from uniform.

Scott Aaronson, Alex Arkhipov

Quantum Inf. Comput., 2014

Quantum POMDPs.

Jennifer Barry, Daniel T. Barry, Scott Aaronson

CoRR, 2014

Weak Parity.

Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

AM with Multiple Merlins.

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

Any Beamsplitter Generates Universal Quantum Linear Optics.

Adam Bouland, Scott Aaronson

Electron. Colloquium Comput. Complex., 2013

BosonSampling Is Far From Uniform.

Scott Aaronson

Electron. Colloquium Comput. Complex., 2013

The Ghost in the Quantum Turing Machine.

Scott Aaronson

CoRR, 2013

Sophistication as Randomness Deficiency.

Francisco Mota, Scott Aaronson, Luis Filipe Coelho Antunes, Andre Souto

Proceedings of the Descriptional Complexity of Formal Systems, 2013

Quantum Computing since Democritus.

Scott Aaronson

Cambridge University Press, ISBN: 978-0-521-19956-8, 2013

2012

Impossibility of succinct quantum proofs for collision-freeness.

Scott Aaronson

Quantum Inf. Comput., 2012

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

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2011

On Circuit Lower Bounds from Derandomization.

Scott Aaronson, Dieter van Melkebeek

Theory Comput., 2011

Special Section on Foundations of Computer Science.

Scott Aaronson, Jeff Erickson, Mohammad Mahdian, R. Ravi, Emanuele Viola

SIAM J. Comput., 2011

Why Philosophers Should Care About Computational Complexity.

Scott Aaronson

Electron. Colloquium Comput. Complex., 2011

A Linear-Optical Proof that the Permanent is #P-Hard.

Scott Aaronson

Electron. Colloquium Comput. Complex., 2011

The One-Way Communication Complexity of Subgroup Membership.

Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani

Chic. J. Theor. Comput. Sci., 2011

The computational complexity of linear optics.

Scott Aaronson, Alex Arkhipov

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

The Need for Structure in Quantum Speedups.

Scott Aaronson, Andris Ambainis

Proceedings of the Innovations in Computer Science, 2011

Advice Coins for Classical and Quantum Computation.

Scott Aaronson, Andrew Drucker

Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

The Equivalence of Sampling and Searching.

Scott Aaronson

Proceedings of the Computer Science - Theory and Applications, 2011

2010

A note on circuit lower bounds from derandomization.

Scott Aaronson, Dieter van Melkebeek

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 Counterexample to the Generalized Linial-Nisan Conjecture.

Scott Aaronson

Electron. Colloquium Comput. Complex., 2010

QIP = PSPACE breakthrough: technical perspective.

Scott Aaronson

Commun. ACM, 2010

A full characterization of quantum advice.

Scott Aaronson, Andrew Drucker

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

BQP and the polynomial hierarchy.

Scott Aaronson

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

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

Proceedings of the Innovations in Computer Science, 2010

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

On perfect completeness for QMA.

Scott Aaronson

Quantum Inf. Comput., 2009

The One-Way Communication Complexity of Group Membership

Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani

CoRR, 2009

Quantum Copy-Protection and Quantum Money.

Scott Aaronson

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Closed Timelike Curves Make Quantum and Classical Computing Equivalent.

Scott Aaronson, John Watrous

Electron. Colloquium Comput. Complex., 2008

Algebrization: a new barrier in complexity theory.

Scott Aaronson, Avi Wigderson

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

The Polynomial Method in Quantum and Classical Computing.

Scott Aaronson

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

The Power of Unentanglement.

Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor

Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, 2008

2007

Review of "The Access Principle by John Willinsky, " MIT Press, 2005.

Scott Aaronson

SIGACT News, 2007

The Limits of Quantum Computers.

Scott Aaronson

Proceedings of the Computer Science, 2007

Quantum versus Classical Proofs and Advice.

Scott Aaronson, Greg Kuperberg

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

The Learnability of Quantum States.

Scott Aaronson

Electron. Colloquium Comput. Complex., 2006

Oracles Are Subtle But Not Malicious.

Scott Aaronson

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols.

Scott Aaronson

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Guest Column: NP-complete problems and physical reality.

Scott Aaronson

SIGACT News, 2005

Quantum lower bound for recursive fourier sampling.

Scott Aaronson

Quantum Inf. Comput., 2005

QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols

Scott Aaronson

Electron. Colloquium Comput. Complex., 2005

NP-complete Problems and Physical Reality

Scott Aaronson

Electron. Colloquium Comput. Complex., 2005

Quantum Computing, Postselection, and Probabilistic Polynomial-Time

Scott Aaronson

Electron. Colloquium Comput. Complex., 2005

The complexity of agreement.

Scott Aaronson

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

2004

Quantum lower bounds for the collision and the element distinctness problems.

Scott Aaronson, Yaoyun Shi

J. ACM, 2004

Improved Simulation of Stabilizer Circuits

Scott Aaronson, Daniel Gottesman

CoRR, 2004

Limits on Efficient Computation in the Physical World

Scott Aaronson

CoRR, 2004

Lower bounds for local search by quantum arguments.

Scott Aaronson

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Multilinear formulas and skepticism of quantum computing.

Scott Aaronson

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Limitations of Quantum Advice and One-Way Communication.

Scott Aaronson

Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 2004

2003

Algorithms for Boolean Function Query Properties.

Scott Aaronson

SIAM J. Comput., 2003

Is P Versus NP Formally Independent?

Scott Aaronson

Bull. EATCS, 2003

Quantum Search of Spatial Regions.

Scott Aaronson, Andris Ambainis

Proceedings of the 44th Symposium on Foundations of Computer Science, 2003

Quantum Certificate Complexity.

Scott Aaronson

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Book review: On "A New Kind of Science" by Stephen Wolfram.

Scott Aaronson

Quantum Inf. Comput., 2002

Quantum lower bound for the collision problem.

Scott Aaronson

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

1997

Optimal Demand-oriented Topology for Hypertext Systems.

Scott Aaronson

Proceedings of the SIGIR '97: Proceedings of the 20th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, 1997