default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDScott Aaronson
Person information
- affiliation: University of Texas at Austin, Department of Computer Science, TX, USA
- affiliation: Massachusetts Institute of Technology (MIT), Department of Electrical Engineering and Computer Science, Cambridge, MA, USA
- affiliation: Institute for Advanced Study, Princeton, NJ, USA
- affiliation: University of Waterloo, Institute for Quantum Computing, ON, Canada
- award (2009): Presidential Early Career Award for Scientists and Engineers
SPARQL queries 
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[c54]Scott Aaronson, Harry Buhrman, William Kretschmer:
A Qubit, a Coin, and an Advice String Walk into a Relational Problem. ITCS 2024: 1:1-1:24- [c53]Scott Aaronson, Adam Bouland
, Bill Fefferman, Soumik Ghosh, Umesh V. Vazirani, Chenyi Zhang, Zixin Zhou:
Quantum Pseudoentanglement. ITCS 2024: 2:1-2:21 - [i136]Scott Aaronson, Sabee Grewal, Vishnu Iyer, Simon C. Marshall, Ronak Ramachandran:
PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements. CoRR abs/2403.02543 (2024) - [i135]Simon C. Marshall, Scott Aaronson, Vedran Dunjko:
Improved separation between quantum and classical computers for sampling and functional tasks. CoRR abs/2410.20935 (2024) - 2023
- [j39]Emre Yolcu, Scott Aaronson, Marijn J. H. Heule:
An Automated Approach to the Collatz Conjecture. J. Autom. Reason. 67(2): 15 (2023) - [c52]Weiyuan Gong, Scott Aaronson:
Learning Distributions over Quantum Measurement Outcomes. ICML 2023: 11598-11613 - [c51]Scott Aaronson, Shih-Han Hung:
Certified Randomness from Quantum Supremacy. STOC 2023: 933-944 - [c50]Scott Aaronson, Sabee Grewal:
Efficient Tomography of Non-Interacting-Fermion States. TQC 2023: 12:1-12:18 - [i134]Scott Aaronson, Harry Buhrman, William Kretschmer:
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. CoRR abs/2302.10332 (2023) - [i133]Scott Aaronson, Shih-Han Hung:
Certified Randomness from Quantum Supremacy. CoRR abs/2303.01625 (2023) - [i132]Ernest Davis, Scott Aaronson:
Testing GPT-4 with Wolfram Alpha and Code Interpreter plug-ins on math and science problems. CoRR abs/2308.05713 (2023) - [i131]Scott Aaronson, Harry Buhrman, William Kretschmer:
A Qubit, a Coin, and an Advice String Walk Into a Relational Problem. Electron. Colloquium Comput. Complex. TR23 (2023) - [i130]Scott Aaronson, Shih-Han Hung:
Certified Randomness from Quantum Supremacy. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [c49]Scott Aaronson, DeVon Ingram, William Kretschmer:
The Acrobatics of BQP. CCC 2022: 20:1-20:17 - [i129]Gary Marcus, Ernest Davis, Scott Aaronson:
A very preliminary analysis of DALL-E 2. CoRR abs/2204.13807 (2022) - [i128]Weiyuan Gong, Scott Aaronson:
Learning Distributions over Quantum Measurement Outcomes. CoRR abs/2209.03007 (2022) - [i127]Scott Aaronson:
How Much Structure Is Needed for Huge Quantum Speedups? CoRR abs/2209.06930 (2022) - [i126]Scott Aaronson, Jason Pollack:
Discrete Bulk Reconstruction. CoRR abs/2210.15601 (2022) - 2021
- [c48]Emre Yolcu, Scott Aaronson, Marijn J. H. Heule:
An Automated Approach to the Collatz Conjecture. CADE 2021: 468-484 - [c47]Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang:
New Approaches for Quantum Copy-Protection. CRYPTO (1) 2021: 526-555 - [c46]Scott Aaronson:
BQP After 28 Years (Invited Talk). FSTTCS 2021: 1:1-1:1 - [c45]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: 1330-1342 - [i125]Scott Aaronson, Sabee Grewal:
Efficient Learning of Non-Interacting Fermion Distributions. CoRR abs/2102.10458 (2021) - [i124]Emre Yolcu, Scott Aaronson, Marijn J. H. Heule:
An Automated Approach to the Collatz Conjecture. CoRR abs/2105.14697 (2021) - [i123]Scott Aaronson:
Open Problems Related to Quantum Query Complexity. CoRR abs/2109.06917 (2021) - [i122]Scott Aaronson, DeVon Ingram, William Kretschmer:
The Acrobatics of BQP. CoRR abs/2111.10409 (2021) - [i121]Scott Aaronson, Andris Ambainis, Andrej Bogdanov, Krishnamoorthy Dinesh, Tsun Ming Cheung:
On quantum versus classical query complexity. Electron. Colloquium Comput. Complex. TR21 (2021) - [i120]Scott Aaronson, DeVon Ingram, William Kretschmer:
The Acrobatics of BQP. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j38]Scott Aaronson:
Shadow Tomography of Quantum States. SIAM J. Comput. 49(5) (2020) - [j37]Scott Aaronson:
The Busy Beaver Frontier. SIGACT News 51(3): 32-54 (2020) - [j36]Scott Aaronson, Sam Gunn:
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking. Theory Comput. 16: 1-8 (2020) - [c44]Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler:
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CCC 2020: 7:1-7:47 - [c43]Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang:
On the Quantum Complexity of Closest Pair and Related Problems. CCC 2020: 16:1-16:43 - [c42]Scott Aaronson, Patrick Rall:
Quantum Approximate Counting, Simplified. SOSA 2020: 24-32 - [i119]Scott Aaronson, Jiahui Liu, Ruizhe Zhang:
Quantum Copy-Protection from Hidden Subspaces. CoRR abs/2004.09674 (2020) - [i118]Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal:
Quantum Implications of Huang's Sensitivity Theorem. CoRR abs/2004.13231 (2020) - [i117]Scott Aaronson, Shalev Ben-David, Robin Kothari, Shravas Rao, Avishay Tal:
Degree vs. Approximate Degree and Quantum Implications of Huang's Sensitivity Theorem. CoRR abs/2010.12629 (2020) - [i116]Scott Aaronson:
The Busy Beaver Frontier. Electron. Colloquium Comput. Complex. TR20 (2020) - [i115]Scott Aaronson, Yosi Atia, Leonard Susskind:
On the Hardness of Detecting Macroscopic Superpositions. Electron. Colloquium Comput. Complex. TR20 (2020) - [i114]Scott Aaronson, Shalev Ben-David, Robin Kothari, Avishay Tal:
Quantum Implications of Huang's Sensitivity Theorem. Electron. Colloquium Comput. Complex. TR20 (2020) - [i113]Scott Aaronson, Jiahui Liu, Qipeng Liu, Mark Zhandry, Ruizhe Zhang:
New Approaches for Quantum Copy-Protection. IACR Cryptol. ePrint Arch. 2020: 1339 (2020)
2010 – 2019
- 2019
- [c41]Scott Aaronson, Daniel Grier, Luke Schaeffer:
A Quantum Query Complexity Trichotomy for Regular Languages. FOCS 2019: 942-965 - [c40]Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi:
Complexity-Theoretic Limitations on Blind Delegated Quantum Computation. ICALP 2019: 6:1-6:13 - [c39]Scott Aaronson, Guy N. Rothblum:
Gentle measurement of quantum states and differential privacy. STOC 2019: 322-333 - [i112]Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler:
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. CoRR abs/1904.08914 (2019) - [i111]Scott Aaronson, Patrick Rall:
Quantum Approximate Counting, Simplified. CoRR abs/1908.10846 (2019) - [i110]Scott Aaronson, Sam Gunn:
On the Classical Hardness of Spoofing Linear Cross-Entropy Benchmarking. CoRR abs/1910.12085 (2019) - [i109]Scott Aaronson, Nai-Hui Chia, Han-Hsuan Lin, Chunhao Wang, Ruizhe Zhang:
On the Quantum Complexity of Closest Pair and Related Problems. CoRR abs/1911.01973 (2019) - [i108]Scott Aaronson, Daniel Grier, Luke Schaeffer:
A Quantum Query Complexity Trichotomy for Regular Languages. Electron. Colloquium Comput. Complex. TR19 (2019) - [i107]Scott Aaronson, Robin Kothari, William Kretschmer, Justin Thaler:
Quantum Lower Bounds for Approximate Counting via Laurent Polynomials. Electron. Colloquium Comput. Complex. TR19 (2019) - [i106]Scott Aaronson, Guy N. Rothblum:
Gentle Measurement of Quantum States and Differential Privacy. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j35]Scott Aaronson:
PDQP/qpoly=ALL. Quantum Inf. Comput. 18(11&12): 901-909 (2018) - [j34]Scott Aaronson, Andris Ambainis:
Forrelation: A Problem That Optimally Separates Quantum from Classical Computing. SIAM J. Comput. 47(3): 982-1038 (2018) - [j33]Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson:
The fewest clues problem. Theor. Comput. Sci. 748: 28-39 (2018) - [c38]Scott Aaronson, Xinyi Chen, Elad Hazan, Satyen Kale, Ashwin Nayak:
Online Learning of Quantum States. NeurIPS 2018: 8976-8986 - [c37]Scott Aaronson:
Shadow tomography of quantum states. STOC 2018: 325-338 - [i105]Scott Aaronson, Xinyi Chen, Elad Hazan, Ashwin Nayak:
Online Learning of Quantum States. CoRR abs/1802.09025 (2018) - [i104]Scott Aaronson:
PDQP/qpoly = ALL. CoRR abs/1805.08577 (2018) - [i103]Scott Aaronson:
Quantum Lower Bound for Approximate Counting Via Laurent Polynomials. CoRR abs/1808.02420 (2018) - [i102]Scott Aaronson, Daniel Grier, Luke Schaeffer:
A Quantum Query Complexity Trichotomy for Regular Languages. CoRR abs/1812.04219 (2018) - [i101]Scott Aaronson:
PDQP/qpoly = ALL. Electron. Colloquium Comput. Complex. TR18 (2018) - [i100]Scott Aaronson:
Quantum Lower Bound for Approximate Counting Via Laurent Polynomials. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [c36]Scott Aaronson, Lijie Chen:
Complexity-Theoretic Foundations of Quantum Supremacy Experiments. CCC 2017: 22:1-22:67 - [c35]Scott Aaronson, Daniel Grier, Luke Schaeffer:
The Classification of Reversible Bit Operations. ITCS 2017: 23:1-23:34 - [c34]Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban:
The computational complexity of ball permutations. STOC 2017: 317-327 - [i99]Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi:
On the implausibility of classical client blind quantum computing. CoRR abs/1704.08482 (2017) - [i98]Scott Aaronson:
Shadow Tomography of Quantum States. CoRR abs/1711.01053 (2017) - [i97]Andrea Rocchetto, Scott Aaronson, Simone Severini, Gonzalo Carvacho, Davide Poderini, Iris Agresti, Marco Bentivegna, Fabio Sciarrino:
Experimental learning of quantum states. CoRR abs/1712.00127 (2017) - [i96]Scott Aaronson:
P=?NP. Electron. Colloquium Comput. Complex. TR17 (2017) - [i95]Scott Aaronson:
Shadow Tomography of Quantum States. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j32]Adam Yedidia, Scott Aaronson:
A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory. Complex Syst. 25(4) (2016) - [c33]Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs:
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CCC 2016: 25:1-25:19 - [c32]Scott Aaronson, Shalev Ben-David:
Sculpting Quantum Speedups. CCC 2016: 26:1-26:28 - [c31]Erik D. Demaine, Fermi Ma, Ariel Schvartzman, Erik Waingarten, Scott Aaronson:
The Fewest Clues Problem. FUN 2016: 12:1-12:12 - [c30]Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee:
The Space "Just Above" BQP. ITCS 2016: 271-280 - [c29]Scott Aaronson, Shalev Ben-David, Robin Kothari:
Separations in query complexity using cheat sheets. STOC 2016: 863-876 - [p2]Scott Aaronson:
The Ghost in the Quantum Turing Machine. The Once and Future Turing 2016: 193-296 - [p1]Scott Aaronson:
P =? NP. Open Problems in Mathematics 2016: 1-122 - [i94]Adam Yedidia, Scott Aaronson:
A Relatively Small Turing Machine Whose Behavior Is Independent of Set Theory. CoRR abs/1605.04343 (2016) - [i93]Scott Aaronson:
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. CoRR abs/1607.05256 (2016) - [i92]Scott Aaronson, Adam Bouland, Greg Kuperberg, Saeed Mehraban:
The Computational Complexity of Ball Permutations. CoRR abs/1610.06646 (2016) - [i91]Scott Aaronson, Lijie Chen:
Complexity-Theoretic Foundations of Quantum Supremacy Experiments. CoRR abs/1612.05903 (2016) - [i90]Scott Aaronson:
The Complexity of Quantum States and Transformations: From Quantum Money to Black Holes. Electron. Colloquium Comput. Complex. TR16 (2016) - [i89]Scott Aaronson, Mohammad Bavarian, Giulio G. Giusteri:
Computability Theory of Closed Timelike Curves. Electron. Colloquium Comput. Complex. TR16 (2016) - [i88]Scott Aaronson, Lijie Chen:
Complexity-Theoretic Foundations of Quantum Supremacy Experiments. Electron. Colloquium Comput. Complex. TR16 (2016) - [i87]Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson:
Doubly infinite separation of quantum information and communication. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j31]Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. Quantum Inf. Comput. 15(11&12): 901-913 (2015) - [c28]Scott Aaronson, Andris Ambainis:
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. STOC 2015: 307-316 - [i86]Scott Aaronson, Daniel Grier, Luke Schaeffer:
The Classification of Reversible Bit Operations. CoRR abs/1504.05155 (2015) - [i85]Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, Scott Aaronson:
Doubly infinite separation of quantum information and communication. CoRR abs/1507.03546 (2015) - [i84]Scott Aaronson, Daniel J. Brod:
BosonSampling with Lost Photons. CoRR abs/1510.05245 (2015) - [i83]Scott Aaronson, Shalev Ben-David, Robin Kothari:
Separations in query complexity using cheat sheets. CoRR abs/1511.01937 (2015) - [i82]Scott Aaronson, Andris Ambainis, Janis Iraids, Martins Kokainis, Juris Smotrovs:
Polynomials, Quantum Query Complexity, and Grothendieck's Inequality. CoRR abs/1511.08682 (2015) - [i81]Scott Aaronson, Shalev Ben-David:
Sculpting Quantum Speedups. CoRR abs/1512.04016 (2015) - [i80]Scott Aaronson, Shalev Ben-David:
Sculpting Quantum Speedups. Electron. Colloquium Comput. Complex. TR15 (2015) - [i79]Scott Aaronson, Shalev Ben-David, Robin Kothari:
Separations in query complexity using cheat sheets. Electron. Colloquium Comput. Complex. TR15 (2015) - [i78]Scott Aaronson, Daniel Grier, Luke Schaeffer:
The Classification of Reversible Bit Operations. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j30]Scott Aaronson:
The Equivalence of Sampling and Searching. Theory Comput. Syst. 55(2): 281-298 (2014) - [j29]Scott Aaronson, Travis Hance:
Generalizing and derandomizing Gurvits's approximation algorithm for the permanent. Quantum Inf. Comput. 14(7-8): 541-559 (2014) - [j28]Scott Aaronson, Alex Arkhipov:
Bosonsampling is far from uniform. Quantum Inf. Comput. 14(15-16): 1383-1423 (2014) - [j27]Scott Aaronson, Andrew Drucker:
A Full Characterization of Quantum Advice. SIAM J. Comput. 43(3): 1131-1183 (2014) - [j26]Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. Theory Comput. 10: 133-166 (2014) - [c27]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. CCC 2014: 44-55 - [c26]Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian:
Weak Parity. ICALP (1) 2014: 26-38 - [i77]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. CoRR abs/1401.6848 (2014) - [i76]Jennifer Barry, Daniel T. Barry, Scott Aaronson:
Quantum POMDPs. CoRR abs/1406.2858 (2014) - [i75]Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. CoRR abs/1408.3193 (2014) - [i74]Scott Aaronson, Andris Ambainis:
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. CoRR abs/1411.5729 (2014) - [i73]Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee:
The space "just above" BQP. CoRR abs/1412.6507 (2014) - [i72]Scott Aaronson, Andris Ambainis:
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Electron. Colloquium Comput. Complex. TR14 (2014) - [i71]Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee:
The space "just above" BQP. Electron. Colloquium Comput. Complex. TR14 (2014) - [i70]Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. Electron. Colloquium Comput. Complex. TR14 (2014) - [i69]Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [b1]Scott Aaronson:
Quantum Computing since Democritus. Cambridge University Press 2013, ISBN 978-0-521-19956-8, pp. I-XXX, 1-370 - [j25]Scott Aaronson, Alex Arkhipov:
The Computational Complexity of Linear Optics. Theory Comput. 9: 143-252 (2013) - [j24]Scott Aaronson, Paul F. Christiano:
Quantum Money from Hidden Subspaces. Theory Comput. 9: 349-401 (2013) - [c25]Francisco Mota, Scott Aaronson, Luis Filipe Coelho Antunes, Andre Souto:
Sophistication as Randomness Deficiency. DCFS 2013: 172-181 - [i68]Scott Aaronson:
The Ghost in the Quantum Turing Machine. CoRR abs/1306.0159 (2013) - [i67]Scott Aaronson, Alex Arkhipov:
BosonSampling Is Far From Uniform. CoRR abs/1309.7460 (2013) - [i66]Adam Bouland, Scott Aaronson:
Any Beamsplitter Generates Universal Quantum Linear Optics. CoRR abs/1310.6718 (2013) - [i65]Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian:
Weak Parity. CoRR abs/1312.0036 (2013) - [i64]Scott Aaronson:
BosonSampling Is Far From Uniform. Electron. Colloquium Comput. Complex. TR13 (2013) - [i63]Scott Aaronson, Andris Ambainis, Kaspars Balodis, Mohammad Bavarian:
Weak Parity. Electron. Colloquium Comput. Complex. TR13 (2013) - [i62]Adam Bouland, Scott Aaronson:
Any Beamsplitter Generates Universal Quantum Linear Optics. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j23]Scott Aaronson, Edward Farhi, David Gosset, Avinatan Hassidim, Jonathan A. Kelner, Andrew Lutomirski:
Quantum money. Commun. ACM 55(8): 84-92 (2012) - [j22]Scott Aaronson:
Impossibility of succinct quantum proofs for collision-freeness. Quantum Inf. Comput. 12(1-2): 21-28 (2012) - [c24]Scott Aaronson, Paul F. Christiano:
Quantum money from hidden subspaces. STOC 2012: 41-60 - [i61]Scott Aaronson, Paul F. Christiano:
Quantum Money from Hidden Subspaces. CoRR abs/1203.4740 (2012) - [i60]Scott Aaronson, Travis Hance:
Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent. CoRR abs/1212.0025 (2012) - [i59]Scott Aaronson, Paul F. Christiano:
Quantum Money from Hidden Subspaces. Electron. Colloquium Comput. Complex. TR12 (2012) - [i58]Scott Aaronson, Travis Hance:
Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent. Electron. Colloquium Comput. Complex. TR12 (2012) - [i57]Scott Aaronson, Paul F. Christiano:
Quantum Money from Hidden Subspaces. IACR Cryptol. ePrint Arch. 2012: 171 (2012) - 2011
- [j21]Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani:
The One-Way Communication Complexity of Subgroup Membership. Chic. J. Theor. Comput. Sci. 2011 (2011) - [j20]Scott Aaronson, Jeff Erickson, Mohammad Mahdian, R. Ravi, Emanuele Viola:
Special Section on Foundations of Computer Science. SIAM J. Comput. 40(3): 770 (2011) - [j19]Scott Aaronson, Dieter van Melkebeek:
On Circuit Lower Bounds from Derandomization. Theory Comput. 7(1): 177-184 (2011) - [c23]Scott Aaronson:
The Equivalence of Sampling and Searching. CSR 2011: 1-14 - [c22]Scott Aaronson, Andrew Drucker:
Advice Coins for Classical and Quantum Computation. ICALP (1) 2011: 61-72 - [c21]Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. ICS 2011: 338-352 - [c20]Scott Aaronson, Alex Arkhipov:
The computational complexity of linear optics. STOC 2011: 333-342 - [i56]Scott Aaronson:
Impossibility of Succinct Quantum Proofs for Collision-Freeness. CoRR abs/1101.0403 (2011) - [i55]Scott Aaronson, Andrew Drucker:
Advice Coins for Classical and Quantum Computation. CoRR abs/1101.5355 (2011) - [i54]Scott Aaronson:
Why Philosophers Should Care About Computational Complexity. CoRR abs/1108.1791 (2011) - [i53]Scott Aaronson:
A Linear-Optical Proof that the Permanent is #P-Hard. CoRR abs/1109.1674 (2011) - [i52]Scott Aaronson:
Quantum Copy-Protection and Quantum Money. CoRR abs/1110.5353 (2011) - [i51]Scott Aaronson:
A Counterexample to the Generalized Linial-Nisan Conjecture. CoRR abs/1110.6126 (2011) - [i50]Scott Aaronson:
Impossibility of Succinct Quantum Proofs for Collision-Freeness. Electron. Colloquium Comput. Complex. TR11 (2011) - [i49]Scott Aaronson:
A Linear-Optical Proof that the Permanent is #P-Hard. Electron. Colloquium Comput. Complex. TR11 (2011) - [i48]Scott Aaronson:
Why Philosophers Should Care About Computational Complexity. Electron. Colloquium Comput. Complex. TR11 (2011) - [i47]Scott Aaronson, Andrew Drucker:
Advice Coins for Classical and Quantum Computation. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j18]Scott Aaronson:
QIP = PSPACE breakthrough: technical perspective. Commun. ACM 53(12): 101 (2010) - [c19]Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan A. Kelner, Avinatan Hassidim, Peter W. Shor:
Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol. ICS 2010: 20-31 - [c18]Scott Aaronson, Andrew Drucker:
A full characterization of quantum advice. STOC 2010: 131-140 - [c17]Scott Aaronson:
BQP and the polynomial hierarchy. STOC 2010: 141-150 - [i46]Scott Aaronson, Andrew Drucker:
A Full Characterization of Quantum Advice. CoRR abs/1004.0377 (2010) - [i45]Scott Aaronson:
The Equivalence of Sampling and Searching. CoRR abs/1009.5104 (2010) - [i44]Scott Aaronson, Alex Arkhipov:
The Computational Complexity of Linear Optics. CoRR abs/1011.3245 (2010) - [i43]Scott Aaronson:
A Counterexample to the Generalized Linial-Nisan Conjecture. Electron. Colloquium Comput. Complex. TR10 (2010) - [i42]Scott Aaronson:
The Equivalence of Sampling and Searching. Electron. Colloquium Comput. Complex. TR10 (2010) - [i41]Scott Aaronson, Alex Arkhipov:
The Computational Complexity of Linear Optics. Electron. Colloquium Comput. Complex. TR10 (2010) - [i40]Scott Aaronson, Baris Aydinlioglu, Harry Buhrman, John M. Hitchcock, Dieter van Melkebeek:
A note on exponential circuit lower bounds from derandomizing Arthur-Merlin games. Electron. Colloquium Comput. Complex. TR10 (2010) - [i39]Scott Aaronson, Andrew Drucker:
A Full Characterization of Quantum Advice. Electron. Colloquium Comput. Complex. TR10 (2010) - [i38]Scott Aaronson, Dieter van Melkebeek:
A note on circuit lower bounds from derandomization. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j17]Scott Aaronson:
On perfect completeness for QMA. Quantum Inf. Comput. 9(1&2): 81-89 (2009) - [j16]Scott Aaronson, Sudipto Guha, Jon M. Kleinberg, Frank McSherry, Dieter van Melkebeek, Amit Sahai:
Special Issue On The Thirty-Eighth Annual ACM Symposium On Theory Of Computing (STOC 2006). SIAM J. Comput. 39(1): vii (2009) - [j15]Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor:
The Power of Unentanglement. Theory Comput. 5(1): 1-42 (2009) - [j14]Scott Aaronson, Avi Wigderson:
Algebrization: A New Barrier in Complexity Theory. ACM Trans. Comput. Theory 1(1): 2:1-2:54 (2009) - [c16]Scott Aaronson:
Quantum Copy-Protection and Quantum Money. CCC 2009: 229-242 - [i37]Scott Aaronson, François Le Gall, Alexander Russell, Seiichiro Tani:
The One-Way Communication Complexity of Group Membership. CoRR abs/0902.3175 (2009) - [i36]Scott Aaronson:
BQP and the Polynomial Hierarchy. CoRR abs/0910.4698 (2009) - [i35]Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. CoRR abs/0911.0996 (2009) - [i34]Scott Aaronson:
BQP and the Polynomial Hierarchy. Electron. Colloquium Comput. Complex. TR09 (2009) - [i33]Scott Aaronson, Andris Ambainis:
The Need for Structure in Quantum Speedups. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j13]Scott Aaronson:
Quantum certificate complexity. J. Comput. Syst. Sci. 74(3): 313-322 (2008) - [c15]Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor:
The Power of Unentanglement. CCC 2008: 223-236 - [c14]Scott Aaronson:
The Polynomial Method in Quantum and Classical Computing. FOCS 2008: 3 - [c13]Scott Aaronson, Avi Wigderson:
Algebrization: a new barrier in complexity theory. STOC 2008: 731-740 - [i32]Scott Aaronson, John Watrous:
Closed Timelike Curves Make Quantum and Classical Computing Equivalent. CoRR abs/0808.2669 (2008) - [i31]Scott Aaronson:
On Perfect Completeness for QMA. Electron. Colloquium Comput. Complex. TR08 (2008) - [i30]Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor:
The Power of Unentanglement. Electron. Colloquium Comput. Complex. TR08 (2008) - [i29]Scott Aaronson, Avi Wigderson:
Algebrization: A New Barrier in Complexity Theory. Electron. Colloquium Comput. Complex. TR08 (2008) - [i28]Scott Aaronson, John Watrous:
Closed Timelike Curves Make Quantum and Classical Computing Equivalent. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j12]Scott Aaronson:
Review of "The Access Principle by John Willinsky, " MIT Press, 2005. SIGACT News 38(4): 19-23 (2007) - [j11]Scott Aaronson, Greg Kuperberg:
Quantum Versus Classical Proofs and Advice. Theory Comput. 3(1): 129-157 (2007) - [c12]Scott Aaronson, Greg Kuperberg:
Quantum versus Classical Proofs and Advice. CCC 2007: 115-128 - [c11]Scott Aaronson:
The Limits of Quantum Computers. CSR 2007: 4 - 2006
- [j10]Scott Aaronson:
Lower Bounds for Local Search by Quantum Arguments. SIAM J. Comput. 35(4): 804-824 (2006) - [c10]Scott Aaronson:
QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols. CCC 2006: 261-273 - [c9]Scott Aaronson:
Oracles Are Subtle But Not Malicious. CCC 2006: 340-354 - [i27]Scott Aaronson, Greg Kuperberg:
Quantum Versus Classical Proofs and Advice. CoRR abs/quant-ph/0604056 (2006) - [i26]Scott Aaronson:
The Learnability of Quantum States. Electron. Colloquium Comput. Complex. TR06 (2006) - [i25]Scott Aaronson, Greg Kuperberg:
Quantum Versus Classical Proofs and Advice. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j9]Scott Aaronson:
Quantum lower bound for recursive fourier sampling. Quantum Inf. Comput. 5(2): 176-177 (2005) - [j8]Scott Aaronson:
Guest Column: NP-complete problems and physical reality. SIGACT News 36(1): 30-52 (2005) - [j7]Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication. Theory Comput. 1(1): 1-28 (2005) - [j6]Scott Aaronson, Andris Ambainis:
Quantum Search of Spatial Regions. Theory Comput. 1(1): 47-79 (2005) - [c8]Scott Aaronson:
The complexity of agreement. STOC 2005: 634-643 - [i24]Scott Aaronson:
Oracles Are Subtle But Not Malicious. CoRR abs/cs/0504048 (2005) - [i23]Scott Aaronson:
NP-complete Problems and Physical Reality. CoRR abs/quant-ph/0502072 (2005) - [i22]Scott Aaronson:
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols. CoRR abs/quant-ph/0510230 (2005) - [i21]Scott Aaronson:
Quantum Computing, Postselection, and Probabilistic Polynomial-Time. Electron. Colloquium Comput. Complex. TR05 (2005) - [i20]Scott Aaronson:
NP-complete Problems and Physical Reality. Electron. Colloquium Comput. Complex. TR05 (2005) - [i19]Scott Aaronson:
Oracles Are Subtle But Not Malicious. Electron. Colloquium Comput. Complex. TR05 (2005) - [i18]Scott Aaronson:
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j5]Scott Aaronson, Yaoyun Shi:
Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51(4): 595-605 (2004) - [c7]Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication. CCC 2004: 320-332 - [c6]Scott Aaronson:
Multilinear formulas and skepticism of quantum computing. STOC 2004: 118-127 - [c5]Scott Aaronson:
Lower bounds for local search by quantum arguments. STOC 2004: 465-474 - [i17]Scott Aaronson:
Limits on Efficient Computation in the Physical World. CoRR abs/quant-ph/0412143 (2004) - [i16]Scott Aaronson:
Quantum Computing, Postselection, and Probabilistic Polynomial-Time. CoRR abs/quant-ph/0412187 (2004) - [i15]Scott Aaronson:
The Complexity of Agreement. CoRR cs.CC/0406061 (2004) - [i14]Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication. CoRR quant-ph/0402095 (2004) - [i13]Scott Aaronson, Daniel Gottesman:
Improved Simulation of Stabilizer Circuits. CoRR quant-ph/0406196 (2004) - [i12]Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication. Electron. Colloquium Comput. Complex. TR04 (2004) - [i11]Scott Aaronson:
The Complexity of Agreement. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j4]Scott Aaronson:
Is P Versus NP Formally Independent? Bull. EATCS 81: 109-136 (2003) - [j3]Scott Aaronson:
Quantum lower bound for recursive Fourier sampling. Quantum Inf. Comput. 3(2): 165-174 (2003) - [j2]Scott Aaronson:
Algorithms for Boolean Function Query Properties. SIAM J. Comput. 32(5): 1140-1157 (2003) - [c4]Scott Aaronson:
Quantum Certificate Complexity. CCC 2003: 171-178 - [c3]Scott Aaronson, Andris Ambainis:
Quantum Search of Spatial Regions. FOCS 2003: 200-209 - [i10]Scott Aaronson:
Lower Bounds for Local Search by Quantum Arguments. CoRR quant-ph/0307149 (2003) - [i9]Scott Aaronson:
Multilinear Formulas and Skepticism of Quantum Computing. CoRR quant-ph/0311039 (2003) - [i8]Scott Aaronson:
Quantum Certificate Complexity. Electron. Colloquium Comput. Complex. TR03 (2003) - [i7]Scott Aaronson:
Lower Bounds for Local Search by Quantum Arguments. Electron. Colloquium Comput. Complex. TR03 (2003) - [i6]Scott Aaronson:
Multilinear Formulas and Skepticism of Quantum Computing. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j1]Scott Aaronson:
Book review: On "A New Kind of Science" by Stephen Wolfram. Quantum Inf. Comput. 2(5): 410-423 (2002) - [c2]Scott Aaronson:
Quantum lower bound for the collision problem. STOC 2002: 635-642 - [i5]Scott Aaronson:
Quantum Lower Bound for Recursive Fourier Sampling. CoRR quant-ph/0209060 (2002) - [i4]Scott Aaronson:
Quantum Certificate Complexity. CoRR quant-ph/0210020 (2002) - [i3]Scott Aaronson:
Quantum Lower Bound for Recursive Fourier Sampling. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [i2]Scott Aaronson:
Algorithms for Boolean Function Query Properties. CoRR cs.CC/0107010 (2001) - [i1]Scott Aaronson:
Quantum Lower Bound for the Collision Problem. CoRR quant-ph/0111102 (2001)
1990 – 1999
- 1997
- [c1]Scott Aaronson:
Optimal Demand-oriented Topology for Hypertext Systems. SIGIR 1997: 168-177
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-01-09 13:13 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
