Scott Aaronson

Publication Activity (10 Years)

Years Active: 1997-2024
Publications (10 Years): 83

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

STOC

Computational Complexity Conference

Publications

Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou
Quantum Pseudoentanglement. ITCS (2024)
Scott Aaronson, Sabee Grewal, Vishnu Iyer, Simon C. Marshall, Ronak Ramachandran
PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements. CoRR (2024)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk into a Relational Problem. ITCS (2024)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. CoRR (2023)
Scott Aaronson, Shih-Han Hung
Certified Randomness from Quantum Supremacy. CoRR (2023)
Weiyuan Gong, Scott Aaronson
Learning Distributions over Quantum Measurement Outcomes. ICML (2023)
Scott Aaronson, Shih-Han Hung
Certified Randomness from Quantum Supremacy. Electron. Colloquium Comput. Complex. (2023)
Ernest Davis, Scott Aaronson
Testing GPT-4 with Wolfram Alpha and Code Interpreter plug-ins on math and science problems. CoRR (2023)
Scott Aaronson, Shih-Han Hung
Certified Randomness from Quantum Supremacy. STOC (2023)
Scott Aaronson, Harry Buhrman, William Kretschmer
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex. (2023)
Emre Yolcu, Scott Aaronson, Marijn J. H. Heule
An Automated Approach to the Collatz Conjecture. J. Autom. Reason. 67 (2) (2023)
Scott Aaronson, Sabee Grewal
Efficient Tomography of Non-Interacting-Fermion States. TQC (2023)
Scott Aaronson
How Much Structure Is Needed for Huge Quantum Speedups? CoRR (2022)
Gary Marcus, Ernest Davis, Scott Aaronson
A very preliminary analysis of DALL-E 2. CoRR (2022)
Weiyuan Gong, Scott Aaronson
Learning Distributions over Quantum Measurement Outcomes. CoRR (2022)
Scott Aaronson, DeVon Ingram, William Kretschmer
The Acrobatics of BQP. CCC (2022)
Scott Aaronson, Jason Pollack
Discrete Bulk Reconstruction. CoRR (2022)
Emre Yolcu, Scott Aaronson, Marijn J. H. Heule
An Automated Approach to the Collatz Conjecture. CoRR (2021)
Scott Aaronson
Open Problems Related to Quantum Query Complexity. CoRR (2021)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. STOC (2021)
Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Cheung Tsun Ming
On quantum versus classical query complexity. Electron. Colloquium Comput. Complex. 28 (2021)
Scott Aaronson, DeVon Ingram, William Kretschmer
The Acrobatics of BQP. Electron. Colloquium Comput. Complex. 28 (2021)
Emre Yolcu, Scott Aaronson, Marijn J. H. Heule
An Automated Approach to the Collatz Conjecture. CADE (2021)
Scott Aaronson, DeVon Ingram, William Kretschmer
The Acrobatics of BQP. CoRR (2021)
Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang
New Approaches for Quantum Copy-Protection. CRYPTO (1) (2021)
Scott Aaronson
BQP After 28 Years (Invited Talk). FSTTCS (2021)
Scott Aaronson, Sabee Grewal
Efficient Learning of Non-Interacting Fermion Distributions. CoRR (2021)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem. CoRR (2020)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Computational Complexity Conference (2020)
Scott Aaronson
Shadow Tomography of Quantum States. SIAM J. Comput. 49 (5) (2020)
Scott Aaronson, Yosi Atia, Leonard Susskind
On the Hardness of Detecting Macroscopic Superpositions. Electron. Colloquium Comput. Complex. 27 (2020)
Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang
New Approaches for Quantum Copy-Protection. IACR Cryptol. ePrint Arch. 2020 (2020)
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang
On the Quantum Complexity of Closest Pair and Related Problems. Computational Complexity Conference (2020)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
Quantum Implications of Huang's Sensitivity Theorem. Electron. Colloquium Comput. Complex. 27 (2020)
Scott Aaronson, Jiahui Liu, Ruizhe Zhang
Quantum Copy-Protection from Hidden Subspaces. CoRR (2020)
Scott Aaronson
The Busy Beaver Frontier. SIGACT News 51 (3) (2020)
Scott Aaronson, Sam Gunn
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking. Theory Comput. 16 (2020)
Scott Aaronson, Patrick Rall
Quantum Approximate Counting, Simplified. SOSA (2020)
Scott Aaronson
The Busy Beaver Frontier. Electron. Colloquium Comput. Complex. 27 (2020)
Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
Quantum Implications of Huang's Sensitivity Theorem. CoRR (2020)
Scott Aaronson, Daniel Grier, Luke Schaeffer
A Quantum Query Complexity Trichotomy for Regular Languages. Electron. Colloquium Comput. Complex. 26 (2019)
Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi
Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. ICALP (2019)
Scott Aaronson, Guy N. Rothblum
Gentle measurement of quantum states and differential privacy. STOC (2019)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Electron. Colloquium Comput. Complex. 26 (2019)
Scott Aaronson, Daniel Grier, Luke Schaeffer
A Quantum Query Complexity Trichotomy for Regular Languages. FOCS (2019)
Scott Aaronson, Patrick Rall
Quantum Approximate Counting, Simplified. CoRR (2019)
Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CoRR (2019)
Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang
On the Quantum Complexity of Closest Pair and Related Problems. CoRR (2019)
Scott Aaronson, Guy N. Rothblum
Gentle Measurement of Quantum States and Differential Privacy. Electron. Colloquium Comput. Complex. 26 (2019)
Scott Aaronson, Sam Gunn
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking. CoRR (2019)
Scott Aaronson, Andris Ambainis
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. SIAM J. Comput. 47 (3) (2018)
Scott Aaronson
Shadow tomography of quantum states. STOC (2018)
Scott Aaronson
PDQP/qpoly=ALL. Quantum Inf. Comput. 18 (11&12) (2018)
Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson
The fewest clues problem. Theor. Comput. Sci. 748 (2018)
Scott Aaronson
Quantum Lower Bound for Approximate Counting Via Laurent Polynomials. CoRR (2018)
Scott Aaronson, Xinyi Chen, Elad Hazan, Ashwin Nayak
Online Learning of Quantum States. CoRR (2018)
Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, Ashwin Nayak
Online Learning of Quantum States. NeurIPS (2018)
Scott Aaronson
Quantum Lower Bound for Approximate Counting Via Laurent Polynomials. Electron. Colloquium Comput. Complex. 25 (2018)
Scott Aaronson, Daniel Grier, Luke Schaeffer
A Quantum Query Complexity Trichotomy for Regular Languages. CoRR (2018)
Scott Aaronson
PDQP/qpoly = ALL. CoRR (2018)
Scott Aaronson
PDQP/qpoly = ALL. Electron. Colloquium Comput. Complex. 25 (2018)
Scott Aaronson, Daniel Grier, Luke Schaeffer
The Classification of Reversible Bit Operations. ITCS (2017)
Scott Aaronson, Lijie Chen
Complexity-Theoretic Foundations of Quantum Supremacy Experiments. Computational Complexity Conference (2017)
Scott Aaronson
Shadow Tomography of Quantum States. Electron. Colloquium Comput. Complex. 24 (2017)
Scott Aaronson
P=?NP. Electron. Colloquium Comput. Complex. 24 (2017)
Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi
On the implausibility of classical client blind quantum computing. CoRR (2017)
Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban
The computational complexity of ball permutations. STOC (2017)
Andrea Rocchetto, Scott Aaronson, Simone Severini, Gonzalo Carvacho, Davide Poderini, Iris Agresti, Marco Bentivegna, Fabio Sciarrino
Experimental learning of quantum states. CoRR (2017)
Scott Aaronson
Shadow Tomography of Quantum States. CoRR (2017)
Scott Aaronson, Lijie Chen
Complexity-Theoretic Foundations of Quantum Supremacy Experiments. CoRR (2016)
Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson
The Fewest Clues Problem. FUN (2016)
Scott Aaronson, Lijie Chen
Complexity-Theoretic Foundations of Quantum Supremacy Experiments. Electron. Colloquium Comput. Complex. 23 (2016)
Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson
Doubly infinite separation of quantum information and communication. Electron. Colloquium Comput. Complex. 23 (2016)
Scott Aaronson, Mohammad Bavarian, Giulio G. Giusteri
Computability Theory of Closed Timelike Curves. Electron. Colloquium Comput. Complex. 23 (2016)
Adam Yedidia, Scott Aaronson
A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory. Complex Syst. 25 (4) (2016)
Scott Aaronson, Shalev Ben-David, Robin Kothari
Separations in query complexity using cheat sheets. STOC (2016)
Scott Aaronson, Shalev Ben-David
Sculpting Quantum Speedups. Computational Complexity Conference (2016)
Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee
The Space "Just Above" BQP. ITCS (2016)
Scott Aaronson
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. CoRR (2016)
Scott Aaronson
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. Electron. Colloquium Comput. Complex. 23 (2016)
Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. Computational Complexity Conference (2016)
Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban
The Computational Complexity of Ball Permutations. CoRR (2016)
Adam Yedidia, Scott Aaronson
A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory. CoRR (2016)
Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CoRR (2015)
Scott Aaronson, Shalev Ben-David, Robin Kothari
Separations in query complexity using cheat sheets. CoRR (2015)
Scott Aaronson, Shalev Ben-David
Sculpting Quantum Speedups. Electron. Colloquium Comput. Complex. 22 (2015)
Scott Aaronson, Shalev Ben-David
Sculpting Quantum Speedups. CoRR (2015)
Scott Aaronson, Shalev Ben-David, Robin Kothari
Separations in query complexity using cheat sheets. Electron. Colloquium Comput. Complex. 22 (2015)
Scott Aaronson, Andris Ambainis
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. STOC (2015)
Scott Aaronson, Daniel Grier, Luke Schaeffer
The Classification of Reversible Bit Operations. Electron. Colloquium Comput. Complex. 22 (2015)
Scott Aaronson, Daniel Grier, Luke Schaeffer
The Classification of Reversible Bit Operations. CoRR (2015)
Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
Quantum lower bound for inverting a permutation with advice. Quantum Inf. Comput. 15 (11&12) (2015)
Scott Aaronson, Daniel J. Brod
BosonSampling with Lost Photons. CoRR (2015)
Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson
Doubly infinite separation of quantum information and communication. CoRR (2015)
Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
AM with Multiple Merlins. Electron. Colloquium Comput. Complex. 21 (2014)
Scott Aaronson, Andris Ambainis
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Electron. Colloquium Comput. Complex. 21 (2014)
Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee
The space "just above" BQP. CoRR (2014)
Scott Aaronson, Andris Ambainis
The Need for Structure in Quantum Speedups. Theory Comput. 10 (2014)
Scott Aaronson, Travis Hance
Generalizing and derandomizing Gurvits's approximation algorithm for the permanent. Quantum Inf. Comput. 14 (7-8) (2014)
Scott Aaronson, Alex Arkhipov
Bosonsampling is far from uniform. Quantum Inf. Comput. 14 (15-16) (2014)

Scott Aaronson.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Scott Aaronson