Stop the war!Остановите войну!
for scientists:
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
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 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]