Scott Aaronson

242 papers A* 23A 22Misc 4Journal 182Unranked 8

Year	Rank	Type	Title / Venue / Authors
2026	J	`jnl`	Future of quantum computing. Quantum Mach. Intell. Scott Aaronson, Andrew M. Childs, Edward Farhi, Aram W. Harrow, Barry C. Sanders
2026	J	`jnl`	Sparsity and Out-of-Distribution Generalization. CoRR Scott Aaronson, Lin Lin Lee, Jiawei Li
2025	J	`jnl`	Certified randomness using a trapped-ion quantum processor. CoRR 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
2025	J	`jnl`	Certified randomness using a trapped-ion quantum processor. Nat. 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
2025	Misc	`conf`	Faster-than-light coordination for networked systems with quantum non-local games. HotNets Venkat Arun, Vijay Chidambaram, Scott Aaronson
2025	A	`conf`	Improved Separation Between Quantum and Classical Computers for Sampling and Functional Tasks. CCC Simon C. Marshall, Scott Aaronson, Vedran Dunjko
2025	J	`jnl`	Limits to black-box amplification in QMA. Electron. Colloquium Comput. Complex. Scott Aaronson, Freek Witteveen
2025	—	`conf`	PDQMA = DQMA = NEXP: QMA with Hidden Variables and Non-Collapsing Measurements. FSTTCS Scott Aaronson, Sabee Grewal, Vishnu Iyer, Simon C. Marshall, Ronak Ramachandran
2025	J	`jnl`	Wide Neural Networks as a Baseline for the Computational No-Coincidence Conjecture. CoRR John Dunbar, Scott Aaronson
2024	A	`conf`	A Qubit, a Coin, and an Advice String Walk into a Relational Problem. ITCS Scott Aaronson, Harry Buhrman, William Kretschmer
2024	J	`jnl`	Improved separation between quantum and classical computers for sampling and functional tasks. CoRR Simon C. Marshall, Scott Aaronson, Vedran Dunjko
2024	J	`jnl`	PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements. CoRR Scott Aaronson, Sabee Grewal, Vishnu Iyer, Simon C. Marshall, Ronak Ramachandran
2024	A	`conf`	Quantum Pseudoentanglement. ITCS Scott Aaronson, Adam Bouland, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou
2023	J	`jnl`	A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. CoRR Scott Aaronson, Harry Buhrman, William Kretschmer
2023	J	`jnl`	A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex. Scott Aaronson, Harry Buhrman, William Kretschmer
2023	J	`jnl`	An Automated Approach to the Collatz Conjecture. J. Autom. Reason. Emre Yolcu, Scott Aaronson, Marijn J. H. Heule
2023	A*	`conf`	Certified Randomness from Quantum Supremacy. STOC Scott Aaronson, Shih-Han Hung
2023	J	`jnl`	Certified Randomness from Quantum Supremacy. CoRR Scott Aaronson, Shih-Han Hung
2023	J	`jnl`	Certified Randomness from Quantum Supremacy. Electron. Colloquium Comput. Complex. Scott Aaronson, Shih-Han Hung
2023	—	`conf`	Efficient Tomography of Non-Interacting-Fermion States. TQC Scott Aaronson, Sabee Grewal
2023	A*	`conf`	Learning Distributions over Quantum Measurement Outcomes. ICML Weiyuan Gong, Scott Aaronson
2023	J	`jnl`	Testing GPT-4 with Wolfram Alpha and Code Interpreter plug-ins on math and science problems. CoRR Ernest Davis, Scott Aaronson
2022	J	`jnl`	A very preliminary analysis of DALL-E 2. CoRR Gary Marcus, Ernest Davis, Scott Aaronson
2022	J	`jnl`	Discrete Bulk Reconstruction. CoRR Scott Aaronson, Jason Pollack
2022	J	`jnl`	How Much Structure Is Needed for Huge Quantum Speedups? CoRR Scott Aaronson
2022	J	`jnl`	Learning Distributions over Quantum Measurement Outcomes. CoRR Weiyuan Gong, Scott Aaronson
2022	A	`conf`	The Acrobatics of BQP. CCC Scott Aaronson, DeVon Ingram, William Kretschmer
2021	A	`conf`	An Automated Approach to the Collatz Conjecture. CADE Emre Yolcu, Scott Aaronson, Marijn J. H. Heule
2021	J	`jnl`	An Automated Approach to the Collatz Conjecture. CoRR Emre Yolcu, Scott Aaronson, Marijn J. H. Heule
2021	—	`conf`	BQP After 28 Years (Invited Talk). FSTTCS Scott Aaronson
2021	A*	`conf`	Degree vs. approximate degree and Quantum implications of Huang's sensitivity theorem. STOC Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
2021	J	`jnl`	Efficient Learning of Non-Interacting Fermion Distributions. CoRR Scott Aaronson, Sabee Grewal
2021	—	`conf`	New Approaches for Quantum Copy-Protection. CRYPTO (1) Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang
2021	J	`jnl`	On quantum versus classical query complexity. Electron. Colloquium Comput. Complex. Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsun Ming Cheung
2021	J	`jnl`	Open Problems Related to Quantum Query Complexity. CoRR Scott Aaronson
2021	J	`jnl`	Open Problems Related to Quantum Query Complexity. ACM Trans. Quantum Comput. Scott Aaronson
2021	J	`jnl`	The Acrobatics of BQP. CoRR Scott Aaronson, DeVon Ingram, William Kretschmer
2021	J	`jnl`	The Acrobatics of BQP. Electron. Colloquium Comput. Complex. Scott Aaronson, DeVon Ingram, William Kretschmer
2020	J	`jnl`	Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem. CoRR Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal
2020	J	`jnl`	New Approaches for Quantum Copy-Protection. IACR Cryptol. ePrint Arch. Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang
2020	J	`jnl`	On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking. Theory Comput. Scott Aaronson, Sam Gunn
2020	J	`jnl`	On the Hardness of Detecting Macroscopic Superpositions. Electron. Colloquium Comput. Complex. Scott Aaronson, Yosi Atia, Leonard Susskind
2020	A	`conf`	On the Quantum Complexity of Closest Pair and Related Problems. CCC Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang
2020	—	`conf`	Quantum Approximate Counting, Simplified. SOSA Scott Aaronson, Patrick Rall
2020	J	`jnl`	Quantum Copy-Protection from Hidden Subspaces. CoRR Scott Aaronson, Jiahui Liu, Ruizhe Zhang
2020	J	`jnl`	Quantum Implications of Huang's Sensitivity Theorem. CoRR Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
2020	J	`jnl`	Quantum Implications of Huang's Sensitivity Theorem. Electron. Colloquium Comput. Complex. Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal
2020	A	`conf`	Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CCC Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
2020	J	`jnl`	Shadow Tomography of Quantum States. SIAM J. Comput. Scott Aaronson
2020	J	`jnl`	The Busy Beaver Frontier. Electron. Colloquium Comput. Complex. Scott Aaronson
2020	J	`jnl`	The Busy Beaver Frontier. SIGACT News Scott Aaronson
2019	A*	`conf`	A Quantum Query Complexity Trichotomy for Regular Languages. FOCS Scott Aaronson, Daniel Grier, Luke Schaeffer
2019	J	`jnl`	A Quantum Query Complexity Trichotomy for Regular Languages. Electron. Colloquium Comput. Complex. Scott Aaronson, Daniel Grier, Luke Schaeffer
2019	A*	`conf`	Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. ICALP Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi
2019	J	`jnl`	Gentle Measurement of Quantum States and Differential Privacy. Electron. Colloquium Comput. Complex. Scott Aaronson, Guy N. Rothblum
2019	A*	`conf`	Gentle measurement of quantum states and differential privacy. STOC Scott Aaronson, Guy N. Rothblum
2019	J	`jnl`	On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking. CoRR Scott Aaronson, Sam Gunn
2019	J	`jnl`	On the Quantum Complexity of Closest Pair and Related Problems. CoRR Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang
2019	J	`jnl`	Quantum Approximate Counting, Simplified. CoRR Scott Aaronson, Patrick Rall
2019	J	`jnl`	Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CoRR Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
2019	J	`jnl`	Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Electron. Colloquium Comput. Complex. Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler
2018	J	`jnl`	A Quantum Query Complexity Trichotomy for Regular Languages. CoRR Scott Aaronson, Daniel Grier, Luke Schaeffer
2018	J	`jnl`	Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. SIAM J. Comput. Scott Aaronson, Andris Ambainis
2018	A*	`conf`	Online Learning of Quantum States. NeurIPS Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, Ashwin Nayak
2018	J	`jnl`	Online Learning of Quantum States. CoRR Scott Aaronson, Xinyi Chen, Elad Hazan, Ashwin Nayak
2018	J	`jnl`	PDQP/qpoly = ALL. CoRR Scott Aaronson
2018	J	`jnl`	PDQP/qpoly = ALL. Electron. Colloquium Comput. Complex. Scott Aaronson
2018	J	`jnl`	PDQP/qpoly=ALL. Quantum Inf. Comput. Scott Aaronson
2018	J	`jnl`	Quantum Lower Bound for Approximate Counting Via Laurent Polynomials. CoRR Scott Aaronson
2018	J	`jnl`	Quantum Lower Bound for Approximate Counting Via Laurent Polynomials. Electron. Colloquium Comput. Complex. Scott Aaronson
2018	A*	`conf`	Shadow tomography of quantum states. STOC Scott Aaronson
2018	J	`jnl`	The fewest clues problem. Theor. Comput. Sci. Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson
2017	A	`conf`	Complexity-Theoretic Foundations of Quantum Supremacy Experiments. CCC Scott Aaronson, Lijie Chen
2017	J	`jnl`	Experimental learning of quantum states. CoRR Andrea Rocchetto, Scott Aaronson, Simone Severini, Gonzalo Carvacho, Davide Poderini, Iris Agresti, Marco Bentivegna, Fabio Sciarrino
2017	J	`jnl`	On the implausibility of classical client blind quantum computing. CoRR Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi
2017	J	`jnl`	P=?NP. Electron. Colloquium Comput. Complex. Scott Aaronson
2017	J	`jnl`	Shadow Tomography of Quantum States. CoRR Scott Aaronson
2017	J	`jnl`	Shadow Tomography of Quantum States. Electron. Colloquium Comput. Complex. Scott Aaronson
2017	A	`conf`	The Classification of Reversible Bit Operations. ITCS Scott Aaronson, Daniel Grier, Luke Schaeffer
2017	A*	`conf`	The computational complexity of ball permutations. STOC Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban
2016	J	`jnl`	A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory. Complex Syst. Adam Yedidia, Scott Aaronson
2016	J	`jnl`	A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory. CoRR Adam Yedidia, Scott Aaronson
2016	J	`jnl`	Complexity-Theoretic Foundations of Quantum Supremacy Experiments. CoRR Scott Aaronson, Lijie Chen
2016	J	`jnl`	Complexity-Theoretic Foundations of Quantum Supremacy Experiments. Electron. Colloquium Comput. Complex. Scott Aaronson, Lijie Chen
2016	J	`jnl`	Computability Theory of Closed Timelike Curves. Electron. Colloquium Comput. Complex. Scott Aaronson, Mohammad Bavarian, Giulio G. Giusteri
2016	J	`jnl`	Doubly infinite separation of quantum information and communication. Electron. Colloquium Comput. Complex. Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson
2016	—	`ch.`	P =? NP Open Problems in Mathematics Scott Aaronson
2016	A	`conf`	Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CCC Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs
2016	A	`conf`	Sculpting Quantum Speedups. CCC Scott Aaronson, Shalev Ben-David
2016	A*	`conf`	Separations in query complexity using cheat sheets. STOC Scott Aaronson, Shalev Ben-David, Robin Kothari
2016	J	`jnl`	The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. CoRR Scott Aaronson
2016	J	`jnl`	The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. Electron. Colloquium Comput. Complex. Scott Aaronson
2016	J	`jnl`	The Computational Complexity of Ball Permutations. CoRR Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban
2016	Misc	`conf`	The Fewest Clues Problem. FUN Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson
2016	—	`ch.`	The Ghost in the Quantum Turing Machine. The Once and Future Turing Scott Aaronson
2016	A	`conf`	The Space "Just Above" BQP. ITCS Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee
2015	J	`jnl`	BosonSampling with Lost Photons. CoRR Scott Aaronson, Daniel J. Brod
2015	J	`jnl`	Doubly infinite separation of quantum information and communication. CoRR Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson
2015	A*	`conf`	Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. STOC Scott Aaronson, Andris Ambainis
2015	J	`jnl`	Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CoRR Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs
2015	J	`jnl`	Quantum lower bound for inverting a permutation with advice. Quantum Inf. Comput. Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
2015	J	`jnl`	Sculpting Quantum Speedups. CoRR Scott Aaronson, Shalev Ben-David
2015	J	`jnl`	Sculpting Quantum Speedups. Electron. Colloquium Comput. Complex. Scott Aaronson, Shalev Ben-David
2015	J	`jnl`	Separations in query complexity using cheat sheets. CoRR Scott Aaronson, Shalev Ben-David, Robin Kothari
2015	J	`jnl`	Separations in query complexity using cheat sheets. Electron. Colloquium Comput. Complex. Scott Aaronson, Shalev Ben-David, Robin Kothari
2015	J	`jnl`	The Classification of Reversible Bit Operations. CoRR Scott Aaronson, Daniel Grier, Luke Schaeffer
2015	J	`jnl`	The Classification of Reversible Bit Operations. Electron. Colloquium Comput. Complex. Scott Aaronson, Daniel Grier, Luke Schaeffer
2014	J	`jnl`	A Full Characterization of Quantum Advice. SIAM J. Comput. Scott Aaronson, Andrew Drucker
2014	A	`conf`	AM with Multiple Merlins. CCC Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
2014	J	`jnl`	AM with Multiple Merlins. CoRR Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
2014	J	`jnl`	AM with Multiple Merlins. Electron. Colloquium Comput. Complex. Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz
2014	J	`jnl`	Bosonsampling is far from uniform. Quantum Inf. Comput. Scott Aaronson, Alex Arkhipov
2014	J	`jnl`	Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. CoRR Scott Aaronson, Andris Ambainis
2014	J	`jnl`	Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Electron. Colloquium Comput. Complex. Scott Aaronson, Andris Ambainis
2014	J	`jnl`	Generalizing and derandomizing Gurvits's approximation algorithm for the permanent. Quantum Inf. Comput. Scott Aaronson, Travis Hance
2014	J	`jnl`	Quantum POMDPs. CoRR Jennifer Barry, Daniel T. Barry, Scott Aaronson
2014	J	`jnl`	Quantum lower bound for inverting a permutation with advice. CoRR Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
2014	J	`jnl`	Quantum lower bound for inverting a permutation with advice. Electron. Colloquium Comput. Complex. Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan
2014	J	`jnl`	The Equivalence of Sampling and Searching. Theory Comput. Syst. Scott Aaronson
2014	J	`jnl`	The Need for Structure in Quantum Speedups. Theory Comput. Scott Aaronson, Andris Ambainis
2014	J	`jnl`	The space "just above" BQP. CoRR Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee
2014	J	`jnl`	The space "just above" BQP. Electron. Colloquium Comput. Complex. Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee
2014	—	`conf`	Weak Parity. ICALP (1) Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
2013	J	`jnl`	Any Beamsplitter Generates Universal Quantum Linear Optics. CoRR Adam Bouland, Scott Aaronson
2013	J	`jnl`	Any Beamsplitter Generates Universal Quantum Linear Optics. Electron. Colloquium Comput. Complex. Adam Bouland, Scott Aaronson
2013	J	`jnl`	BosonSampling Is Far From Uniform. CoRR Scott Aaronson, Alex Arkhipov
2013	J	`jnl`	BosonSampling Is Far From Uniform. Electron. Colloquium Comput. Complex. Scott Aaronson
2013	—	`book`	Quantum Computing since Democritus. Scott Aaronson
2013	J	`jnl`	Quantum Money from Hidden Subspaces. Theory Comput. Scott Aaronson, Paul F. Christiano
2013	—	`conf`	Sophistication as Randomness Deficiency. DCFS Francisco Mota, Scott Aaronson, Luis Filipe Coelho Antunes, Andre Souto
2013	J	`jnl`	The Computational Complexity of Linear Optics. Theory Comput. Scott Aaronson, Alex Arkhipov
2013	J	`jnl`	The Ghost in the Quantum Turing Machine. CoRR Scott Aaronson
2013	J	`jnl`	Weak Parity. CoRR Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
2013	J	`jnl`	Weak Parity. Electron. Colloquium Comput. Complex. Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian
2012	J	`jnl`	Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent CoRR Scott Aaronson, Travis Hance
2012	J	`jnl`	Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent. Electron. Colloquium Comput. Complex. Scott Aaronson, Travis Hance
2012	J	`jnl`	Impossibility of succinct quantum proofs for collision-freeness. Quantum Inf. Comput. Scott Aaronson
2012	J	`jnl`	Quantum Money from Hidden Subspaces CoRR Scott Aaronson, Paul F. Christiano
2012	J	`jnl`	Quantum Money from Hidden Subspaces. Electron. Colloquium Comput. Complex. Scott Aaronson, Paul F. Christiano
2012	J	`jnl`	Quantum Money from Hidden Subspaces. IACR Cryptol. ePrint Arch. Scott Aaronson, Paul F. Christiano
2012	A*	`conf`	Quantum money from hidden subspaces. STOC Scott Aaronson, Paul F. Christiano
2012	J	`jnl`	Quantum money. Commun. ACM Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan A. Kelner, Andrew Lutomirski
2011	J	`jnl`	A Counterexample to the Generalized Linial-Nisan Conjecture CoRR Scott Aaronson
2011	J	`jnl`	A Linear-Optical Proof that the Permanent is #P-Hard CoRR Scott Aaronson
2011	J	`jnl`	A Linear-Optical Proof that the Permanent is #P-Hard. Electron. Colloquium Comput. Complex. Scott Aaronson
2011	J	`jnl`	Advice Coins for Classical and Quantum Computation CoRR Scott Aaronson, Andrew Drucker
2011	—	`conf`	Advice Coins for Classical and Quantum Computation. ICALP (1) Scott Aaronson, Andrew Drucker
2011	J	`jnl`	Advice Coins for Classical and Quantum Computation. Electron. Colloquium Comput. Complex. Scott Aaronson, Andrew Drucker
2011	J	`jnl`	Impossibility of Succinct Quantum Proofs for Collision-Freeness CoRR Scott Aaronson
2011	J	`jnl`	Impossibility of Succinct Quantum Proofs for Collision-Freeness. Electron. Colloquium Comput. Complex. Scott Aaronson
2011	J	`jnl`	On Circuit Lower Bounds from Derandomization. Theory Comput. Scott Aaronson, Dieter van Melkebeek
2011	J	`jnl`	Quantum Copy-Protection and Quantum Money CoRR Scott Aaronson
2011	J	`jnl`	Special Section on Foundations of Computer Science. SIAM J. Comput. Scott Aaronson, Jeff Erickson, Mohammad Mahdian, R. Ravi, Emanuele Viola
2011	Misc	`conf`	The Equivalence of Sampling and Searching. CSR Scott Aaronson
2011	A	`conf`	The Need for Structure in Quantum Speedups. ICS Scott Aaronson, Andris Ambainis
2011	J	`jnl`	The One-Way Communication Complexity of Subgroup Membership. Chic. J. Theor. Comput. Sci. Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani
2011	A*	`conf`	The computational complexity of linear optics. STOC Scott Aaronson, Alex Arkhipov
2011	J	`jnl`	Why Philosophers Should Care About Computational Complexity CoRR Scott Aaronson
2011	J	`jnl`	Why Philosophers Should Care About Computational Complexity. Electron. Colloquium Comput. Complex. Scott Aaronson
2010	J	`jnl`	A Counterexample to the Generalized Linial-Nisan Conjecture. Electron. Colloquium Comput. Complex. Scott Aaronson
2010	J	`jnl`	A Full Characterization of Quantum Advice CoRR Scott Aaronson, Andrew Drucker
2010	J	`jnl`	A Full Characterization of Quantum Advice. Electron. Colloquium Comput. Complex. Scott Aaronson, Andrew Drucker
2010	A*	`conf`	A full characterization of quantum advice. STOC Scott Aaronson, Andrew Drucker
2010	J	`jnl`	A note on circuit lower bounds from derandomization. Electron. Colloquium Comput. Complex. Scott Aaronson, Dieter van Melkebeek
2010	J	`jnl`	A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Electron. Colloquium Comput. Complex. Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek
2010	A*	`conf`	BQP and the polynomial hierarchy. STOC Scott Aaronson
2010	A	`conf`	Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol. ICS Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan A. Kelner, Avinatan Hassidim, Peter W. Shor
2010	J	`jnl`	QIP = PSPACE breakthrough: technical perspective. Commun. ACM Scott Aaronson
2010	J	`jnl`	The Computational Complexity of Linear Optics CoRR Scott Aaronson, Alex Arkhipov
2010	J	`jnl`	The Computational Complexity of Linear Optics. Electron. Colloquium Comput. Complex. Scott Aaronson, Alex Arkhipov
2010	J	`jnl`	The Equivalence of Sampling and Searching CoRR Scott Aaronson
2010	J	`jnl`	The Equivalence of Sampling and Searching. Electron. Colloquium Comput. Complex. Scott Aaronson
2009	J	`jnl`	Algebrization: A New Barrier in Complexity Theory. ACM Trans. Comput. Theory Scott Aaronson, Avi Wigderson
2009	J	`jnl`	BQP and the Polynomial Hierarchy CoRR Scott Aaronson
2009	J	`jnl`	BQP and the Polynomial Hierarchy. Electron. Colloquium Comput. Complex. Scott Aaronson
2009	J	`jnl`	On perfect completeness for QMA. Quantum Inf. Comput. Scott Aaronson
2009	A	`conf`	Quantum Copy-Protection and Quantum Money. CCC Scott Aaronson
2009	J	`jnl`	Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006). SIAM J. Comput. Scott Aaronson, Sudipto Guha, Jon M. Kleinberg, Frank McSherry, Dieter van Melkebeek, Amit Sahai
2009	J	`jnl`	The Need for Structure in Quantum Speedups CoRR Scott Aaronson, Andris Ambainis
2009	J	`jnl`	The Need for Structure in Quantum Speedups. Electron. Colloquium Comput. Complex. Scott Aaronson, Andris Ambainis
2009	J	`jnl`	The One-Way Communication Complexity of Group Membership CoRR Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani
2009	J	`jnl`	The Power of Unentanglement. Theory Comput. Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor
2008	J	`jnl`	Algebrization: A New Barrier in Complexity Theory. Electron. Colloquium Comput. Complex. Scott Aaronson, Avi Wigderson
2008	A*	`conf`	Algebrization: a new barrier in complexity theory. STOC Scott Aaronson, Avi Wigderson
2008	J	`jnl`	Closed Timelike Curves Make Quantum and Classical Computing Equivalent. CoRR Scott Aaronson, John Watrous
2008	J	`jnl`	Closed Timelike Curves Make Quantum and Classical Computing Equivalent. Electron. Colloquium Comput. Complex. Scott Aaronson, John Watrous
2008	J	`jnl`	On Perfect Completeness for QMA. Electron. Colloquium Comput. Complex. Scott Aaronson
2008	J	`jnl`	Quantum certificate complexity. J. Comput. Syst. Sci. Scott Aaronson
2008	A*	`conf`	The Polynomial Method in Quantum and Classical Computing. FOCS Scott Aaronson
2008	A	`conf`	The Power of Unentanglement. CCC Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor
2008	J	`jnl`	The Power of Unentanglement. Electron. Colloquium Comput. Complex. Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor
2007	J	`jnl`	Quantum Versus Classical Proofs and Advice. Theory Comput. Scott Aaronson, Greg Kuperberg
2007	A	`conf`	Quantum versus Classical Proofs and Advice. CCC Scott Aaronson, Greg Kuperberg
2007	J	`jnl`	Review of "The Access Principle by John Willinsky, " MIT Press, 2005. SIGACT News Scott Aaronson
2007	Misc	`conf`	The Limits of Quantum Computers. CSR Scott Aaronson
2006	J	`jnl`	Lower Bounds for Local Search by Quantum Arguments. SIAM J. Comput. Scott Aaronson
2006	A	`conf`	Oracles Are Subtle But Not Malicious. CCC Scott Aaronson
2006	A	`conf`	QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols. CCC Scott Aaronson
2006	J	`jnl`	Quantum Versus Classical Proofs and Advice CoRR Scott Aaronson, Greg Kuperberg
2006	J	`jnl`	Quantum Versus Classical Proofs and Advice. Electron. Colloquium Comput. Complex. Scott Aaronson, Greg Kuperberg
2006	J	`jnl`	The Learnability of Quantum States. Electron. Colloquium Comput. Complex. Scott Aaronson
2005	J	`jnl`	Guest Column: NP-complete problems and physical reality. SIGACT News Scott Aaronson
2005	J	`jnl`	Limitations of Quantum Advice and One-Way Communication. Theory Comput. Scott Aaronson
2005	J	`jnl`	NP-complete Problems and Physical Reality CoRR Scott Aaronson
2005	J	`jnl`	NP-complete Problems and Physical Reality Electron. Colloquium Comput. Complex. Scott Aaronson
2005	J	`jnl`	Oracles Are Subtle But Not Malicious CoRR Scott Aaronson
2005	J	`jnl`	Oracles Are Subtle But Not Malicious Electron. Colloquium Comput. Complex. Scott Aaronson
2005	J	`jnl`	QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols CoRR Scott Aaronson
2005	J	`jnl`	QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols Electron. Colloquium Comput. Complex. Scott Aaronson
2005	J	`jnl`	Quantum Computing, Postselection, and Probabilistic Polynomial-Time Electron. Colloquium Comput. Complex. Scott Aaronson
2005	J	`jnl`	Quantum Search of Spatial Regions. Theory Comput. Scott Aaronson, Andris Ambainis
2005	J	`jnl`	Quantum lower bound for recursive fourier sampling. Quantum Inf. Comput. Scott Aaronson
2005	A*	`conf`	The complexity of agreement. STOC Scott Aaronson
2004	J	`jnl`	Improved Simulation of Stabilizer Circuits CoRR Scott Aaronson, Daniel Gottesman
2004	J	`jnl`	Limitations of Quantum Advice and One-Way Communication CoRR Scott Aaronson
2004	J	`jnl`	Limitations of Quantum Advice and One-Way Communication Electron. Colloquium Comput. Complex. Scott Aaronson
2004	A	`conf`	Limitations of Quantum Advice and One-Way Communication. CCC Scott Aaronson
2004	J	`jnl`	Limits on Efficient Computation in the Physical World CoRR Scott Aaronson
2004	A*	`conf`	Lower bounds for local search by quantum arguments. STOC Scott Aaronson
2004	A*	`conf`	Multilinear formulas and skepticism of quantum computing. STOC Scott Aaronson
2004	J	`jnl`	Quantum Computing, Postselection, and Probabilistic Polynomial-Time CoRR Scott Aaronson
2004	J	`jnl`	Quantum lower bounds for the collision and the element distinctness problems. J. ACM Scott Aaronson, Yaoyun Shi
2004	J	`jnl`	The Complexity of Agreement CoRR Scott Aaronson
2004	J	`jnl`	The Complexity of Agreement Electron. Colloquium Comput. Complex. Scott Aaronson
2003	J	`jnl`	Algorithms for Boolean Function Query Properties. SIAM J. Comput. Scott Aaronson
2003	J	`jnl`	Is P Versus NP Formally Independent? Bull. EATCS Scott Aaronson
2003	J	`jnl`	Lower Bounds for Local Search by Quantum Arguments CoRR Scott Aaronson
2003	J	`jnl`	Lower Bounds for Local Search by Quantum Arguments Electron. Colloquium Comput. Complex. Scott Aaronson
2003	J	`jnl`	Multilinear Formulas and Skepticism of Quantum Computing CoRR Scott Aaronson
2003	J	`jnl`	Multilinear Formulas and Skepticism of Quantum Computing Electron. Colloquium Comput. Complex. Scott Aaronson
2003	J	`jnl`	Quantum Certificate Complexity Electron. Colloquium Comput. Complex. Scott Aaronson
2003	A	`conf`	Quantum Certificate Complexity. CCC Scott Aaronson
2003	A*	`conf`	Quantum Search of Spatial Regions. FOCS Scott Aaronson, Andris Ambainis
2003	J	`jnl`	Quantum lower bound for recursive Fourier sampling. Quantum Inf. Comput. Scott Aaronson
2002	J	`jnl`	Book review: On "A New Kind of Science" by Stephen Wolfram. Quantum Inf. Comput. Scott Aaronson
2002	J	`jnl`	Quantum Certificate Complexity CoRR Scott Aaronson
2002	J	`jnl`	Quantum Lower Bound for Recursive Fourier Sampling CoRR Scott Aaronson
2002	J	`jnl`	Quantum Lower Bound for Recursive Fourier Sampling Electron. Colloquium Comput. Complex. Scott Aaronson
2002	A*	`conf`	Quantum lower bound for the collision problem. STOC Scott Aaronson
2001	J	`jnl`	Algorithms for Boolean Function Query Properties CoRR Scott Aaronson
2001	J	`jnl`	Quantum Lower Bound for the Collision Problem CoRR Scott Aaronson
1997	A*	`conf`	Optimal Demand-oriented Topology for Hypertext Systems. SIGIR Scott Aaronson