Scott Aaronson

Affiliations:

University of Texas at Austin, Department of Computer Science, TX, USA
Massachusetts Institute of Technology (MIT), Department of Electrical Engineering and Computer Science, Cambridge, MA, USA
Institute for Advanced Study, Princeton, NJ, USA
University of Waterloo, Institute for Quantum Computing, ON, Canada

According to our database¹, Scott Aaronson authored at least 116 papers between 1997 and 2024.

Collaborative distances:

Dijkstra number² of three.
Erdős number³ of three.

Timeline

Legend:

Book

In proceedings

Article

PhD thesis

Dataset

Other

Bibliography

2024

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements.

[BibT_eX]

[DOI]

CoRR, 2024

Quantum Pseudoentanglement.

[BibT_eX]

[DOI]

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

2023

An Automated Approach to the Collatz Conjecture.

[BibT_eX]

[DOI]

Emre Yolcu

Scott Aaronson

Marijn J. H. Heule

J. Autom. Reason., June, 2023

Certified Randomness from Quantum Supremacy.

[BibT_eX]

[DOI]

Scott Aaronson

Shih-Han Hung

Electron. Colloquium Comput. Complex., 2023

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

[BibT_eX]

[DOI]

Scott Aaronson

Harry Buhrman

William Kretschmer

Electron. Colloquium Comput. Complex., 2023

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

[BibT_eX]

[DOI]

Ernest Davis

Scott Aaronson

CoRR, 2023

Efficient Tomography of Non-Interacting-Fermion States.

[BibT_eX]

[DOI]

Scott Aaronson

Sabee Grewal

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

Learning Distributions over Quantum Measurement Outcomes.

[BibT_eX]

[DOI]

Weiyuan Gong

Scott Aaronson

Proceedings of the International Conference on Machine Learning, 2023

2022

Discrete Bulk Reconstruction.

[BibT_eX]

[DOI]

Scott Aaronson

Jason Pollack

CoRR, 2022

How Much Structure Is Needed for Huge Quantum Speedups?

[BibT_eX]

[DOI]

Scott Aaronson

CoRR, 2022

A very preliminary analysis of DALL-E 2.

[BibT_eX]

[DOI]

Gary Marcus

Ernest Davis

Scott Aaronson

CoRR, 2022

2021

The Acrobatics of BQP.

[BibT_eX]

[DOI]

Scott Aaronson

DeVon Ingram

William Kretschmer

Electron. Colloquium Comput. Complex., 2021

On quantum versus classical query complexity.

[BibT_eX]

[DOI]

Scott Aaronson

Andris Ambainis

Andrej Bogdanov

Krishnamoorthy Dinesh

Tsun Ming Cheung

Electron. Colloquium Comput. Complex., 2021

Open Problems Related to Quantum Query Complexity.

[BibT_eX]

[DOI]

Scott Aaronson

CoRR, 2021

Efficient Learning of Non-Interacting Fermion Distributions.

[BibT_eX]

[DOI]

Scott Aaronson

Sabee Grewal

CoRR, 2021

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

[BibT_eX]

[DOI]

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

BQP After 28 Years (Invited Talk).

[BibT_eX]

[DOI]

Scott Aaronson

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

2020

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

[BibT_eX]

[DOI]

Scott Aaronson

Sam Gunn

Theory Comput., 2020

The Busy Beaver Frontier.

[BibT_eX]

[DOI]

Scott Aaronson

SIGACT News, 2020

Shadow Tomography of Quantum States.

[BibT_eX]

[DOI]

Scott Aaronson

SIAM J. Comput., 2020

New Approaches for Quantum Copy-Protection.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2020

Quantum Implications of Huang's Sensitivity Theorem.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

On the Hardness of Detecting Macroscopic Superpositions.

[BibT_eX]

[DOI]

Scott Aaronson

Yosi Atia

Leonard Susskind

Electron. Colloquium Comput. Complex., 2020

Quantum Copy-Protection from Hidden Subspaces.

[BibT_eX]

[DOI]

Scott Aaronson

Jiahui Liu

Ruizhe Zhang

CoRR, 2020

Quantum Approximate Counting, Simplified.

[BibT_eX]

[DOI]

Scott Aaronson

Patrick Rall

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

On the Quantum Complexity of Closest Pair and Related Problems.

[BibT_eX]

[DOI]

Proceedings of the 35th Computational Complexity Conference, 2020

2019

Gentle Measurement of Quantum States and Differential Privacy.

[BibT_eX]

[DOI]

Scott Aaronson

Guy N. Rothblum

Electron. Colloquium Comput. Complex., 2019

Quantum Lower Bounds for Approximate Counting via Laurent Polynomials.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

A Quantum Query Complexity Trichotomy for Regular Languages.

[BibT_eX]

[DOI]

Scott Aaronson

Daniel Grier

Luke Schaeffer

Electron. Colloquium Comput. Complex., 2019

Complexity-Theoretic Limitations on Blind Delegated Quantum Computation.

[BibT_eX]

[DOI]

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

2018

The fewest clues problem.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2018

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

[BibT_eX]

[DOI]

Scott Aaronson

Andris Ambainis

SIAM J. Comput., 2018

Quantum Lower Bound for Approximate Counting Via Laurent Polynomials.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2018

PDQP/qpoly = ALL.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2018

Online Learning of Quantum States.

[BibT_eX]

[DOI]

CoRR, 2018

Online Learning of Quantum States.

[BibT_eX]

[DOI]

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

2017

P=?NP.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2017

Experimental learning of quantum states.

[BibT_eX]

[DOI]

CoRR, 2017

On the implausibility of classical client blind quantum computing.

[BibT_eX]

[DOI]

CoRR, 2017

The computational complexity of ball permutations.

[BibT_eX]

[DOI]

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

2016

Doubly infinite separation of quantum information and communication.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Complexity-Theoretic Foundations of Quantum Supremacy Experiments.

[BibT_eX]

[DOI]

Scott Aaronson

Lijie Chen

Electron. Colloquium Comput. Complex., 2016

Computability Theory of Closed Timelike Curves.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2016

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

[BibT_eX]

[DOI]

Adam Yedidia

Scott Aaronson

Complex Syst., 2016

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

[BibT_eX]

[DOI]

Proceedings of the 31st Conference on Computational Complexity, 2016

P =? NP

[BibT_eX]

[DOI]

Scott Aaronson

Proceedings of the Open Problems in Mathematics., 2016

The Ghost in the Quantum Turing Machine.

[BibT_eX]

[DOI]

Scott Aaronson

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

2015

The Classification of Reversible Bit Operations.

[BibT_eX]

[DOI]

Scott Aaronson

Daniel Grier

Luke Schaeffer

Electron. Colloquium Comput. Complex., 2015

Separations in query complexity using cheat sheets.

[BibT_eX]

[DOI]

Scott Aaronson

Shalev Ben-David

Robin Kothari

Electron. Colloquium Comput. Complex., 2015

Sculpting Quantum Speedups.

[BibT_eX]

[DOI]

Scott Aaronson

Shalev Ben-David

Electron. Colloquium Comput. Complex., 2015

BosonSampling with Lost Photons.

[BibT_eX]

[DOI]

Scott Aaronson

Daniel J. Brod

CoRR, 2015

2014

A Full Characterization of Quantum Advice.

[BibT_eX]

[DOI]

Scott Aaronson

Andrew Drucker

SIAM J. Comput., 2014

Bosonsampling is far from uniform.

[BibT_eX]

[DOI]

Scott Aaronson

Alex Arkhipov

Quantum Inf. Comput., 2014

Quantum lower bound for inverting a permutation with advice.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

AM with Multiple Merlins.

[BibT_eX]

[DOI]

Scott Aaronson

Russell Impagliazzo

Dana Moshkovitz

Electron. Colloquium Comput. Complex., 2014

The space "just above" BQP.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2014

Quantum POMDPs.

[BibT_eX]

[DOI]

Jennifer Barry

Daniel T. Barry

Scott Aaronson

CoRR, 2014

2013

Any Beamsplitter Generates Universal Quantum Linear Optics.

[BibT_eX]

[DOI]

Adam Bouland

Scott Aaronson

Electron. Colloquium Comput. Complex., 2013

Weak Parity.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

BosonSampling Is Far From Uniform.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2013

The Ghost in the Quantum Turing Machine.

[BibT_eX]

[DOI]

Scott Aaronson

CoRR, 2013

Sophistication as Randomness Deficiency.

[BibT_eX]

[DOI]

Francisco Mota

Scott Aaronson

Luis Filipe Coelho Antunes

Andre Souto

Proceedings of the Descriptional Complexity of Formal Systems, 2013

Quantum Computing since Democritus.

[BibT_eX]

[DOI]

Scott Aaronson

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

2012

Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent.

[BibT_eX]

[DOI]

Scott Aaronson

Travis Hance

Electron. Colloquium Comput. Complex., 2012

Quantum Money from Hidden Subspaces.

[BibT_eX]

[DOI]

Scott Aaronson

Paul F. Christiano

Electron. Colloquium Comput. Complex., 2012

Quantum money.

[BibT_eX]

[DOI]

Commun. ACM, 2012

2011

On Circuit Lower Bounds from Derandomization.

[BibT_eX]

[DOI]

Scott Aaronson

Dieter van Melkebeek

Theory Comput., 2011

Special Section on Foundations of Computer Science.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Advice Coins for Classical and Quantum Computation.

[BibT_eX]

[DOI]

Scott Aaronson

Andrew Drucker

Electron. Colloquium Comput. Complex., 2011

Why Philosophers Should Care About Computational Complexity.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2011

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

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2011

Impossibility of Succinct Quantum Proofs for Collision-Freeness.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2011

The One-Way Communication Complexity of Subgroup Membership.

[BibT_eX]

[DOI]

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

2010

A note on circuit lower bounds from derandomization.

[BibT_eX]

[DOI]

Scott Aaronson

Dieter van Melkebeek

Electron. Colloquium Comput. Complex., 2010

A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

The Computational Complexity of Linear Optics.

[BibT_eX]

[DOI]

Scott Aaronson

Alex Arkhipov

Electron. Colloquium Comput. Complex., 2010

The Equivalence of Sampling and Searching.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2010

A Counterexample to the Generalized Linial-Nisan Conjecture.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2010

QIP = PSPACE breakthrough: technical perspective.

[BibT_eX]

[DOI]

Scott Aaronson

Commun. ACM, 2010

Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2010

2009

Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006).

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

The Need for Structure in Quantum Speedups.

[BibT_eX]

[DOI]

Scott Aaronson

Andris Ambainis

Electron. Colloquium Comput. Complex., 2009

BQP and the Polynomial Hierarchy.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2009

The One-Way Communication Complexity of Group Membership

[BibT_eX]

[DOI]

CoRR, 2009

Quantum Copy-Protection and Quantum Money.

[BibT_eX]

[DOI]

Scott Aaronson

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

2008

Quantum certificate complexity.

[BibT_eX]

[DOI]

Scott Aaronson

J. Comput. Syst. Sci., 2008

Closed Timelike Curves Make Quantum and Classical Computing Equivalent.

[BibT_eX]

[DOI]

Scott Aaronson

John Watrous

Electron. Colloquium Comput. Complex., 2008

Algebrization: A New Barrier in Complexity Theory.

[BibT_eX]

[DOI]

Scott Aaronson

Avi Wigderson

Electron. Colloquium Comput. Complex., 2008

The Power of Unentanglement.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

On Perfect Completeness for QMA.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2008

The Polynomial Method in Quantum and Classical Computing.

[BibT_eX]

[DOI]

Scott Aaronson

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

2007

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

[BibT_eX]

[DOI]

Scott Aaronson

SIGACT News, 2007

The Limits of Quantum Computers.

[BibT_eX]

[DOI]

Scott Aaronson

Proceedings of the Computer Science, 2007

2006

Lower Bounds for Local Search by Quantum Arguments.

[BibT_eX]

[DOI]

Scott Aaronson

SIAM J. Comput., 2006

Quantum Versus Classical Proofs and Advice.

[BibT_eX]

[DOI]

Scott Aaronson

Greg Kuperberg

Electron. Colloquium Comput. Complex., 2006

The Learnability of Quantum States.

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2006

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

[BibT_eX]

[DOI]

Scott Aaronson

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

2005

Quantum Search of Spatial Regions.

[BibT_eX]

[DOI]

Scott Aaronson

Andris Ambainis

Theory Comput., 2005

Guest Column: NP-complete problems and physical reality.

[BibT_eX]

[DOI]

Scott Aaronson

SIGACT News, 2005

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

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2005

Oracles Are Subtle But Not Malicious

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2005

NP-complete Problems and Physical Reality

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2005

Quantum Computing, Postselection, and Probabilistic Polynomial-Time

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2005

2004

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

[BibT_eX]

[DOI]

Scott Aaronson

Yaoyun Shi

J. ACM, 2004

The Complexity of Agreement

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2004

Limitations of Quantum Advice and One-Way Communication

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2004

Improved Simulation of Stabilizer Circuits

[BibT_eX]

[DOI]

Scott Aaronson

Daniel Gottesman

CoRR, 2004

Limits on Efficient Computation in the Physical World

[BibT_eX]

[DOI]

Scott Aaronson

CoRR, 2004

2003

Algorithms for Boolean Function Query Properties.

[BibT_eX]

[DOI]

Scott Aaronson

SIAM J. Comput., 2003

Multilinear Formulas and Skepticism of Quantum Computing

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2003

Is P Versus NP Formally Independent?

[BibT_eX]

Scott Aaronson

Bull. EATCS, 2003

2002

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

[BibT_eX]

[DOI]

Scott Aaronson

Quantum Inf. Comput., 2002

Quantum Lower Bound for Recursive Fourier Sampling

[BibT_eX]

[DOI]

Scott Aaronson

Electron. Colloquium Comput. Complex., 2002

Quantum lower bound for the collision problem.

[BibT_eX]

[DOI]

Scott Aaronson

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

1997

Optimal Demand-oriented Topology for Hypertext Systems.

[BibT_eX]

[DOI]

Scott Aaronson

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

Scott Aaronson

Timeline

Legend:

Links

Online presence:

On csauthors.net:

Bibliography

Loading...