| 2009 |
|---|
| 58 | EE | Scott Aaronson,
François Le Gall,
Alexander Russell,
Seiichiro Tani:
The One-Way Communication Complexity of Group Membership
CoRR abs/0902.3175: (2009) |
| 2008 |
|---|
| 57 | EE | Scott Aaronson:
The Polynomial Method in Quantum and Classical Computing.
FOCS 2008: 3 |
| 56 | EE | Scott Aaronson,
Salman Beigi,
Andrew Drucker,
Bill Fefferman,
Peter W. Shor:
The Power of Unentanglement.
IEEE Conference on Computational Complexity 2008: 223-236 |
| 55 | EE | Scott Aaronson,
Avi Wigderson:
Algebrization: a new barrier in complexity theory.
STOC 2008: 731-740 |
| 54 | EE | Scott Aaronson,
Avi Wigderson:
Algebrization: A New Barrier in Complexity Theory.
Electronic Colloquium on Computational Complexity (ECCC) 15(005): (2008) |
| 53 | EE | Scott Aaronson,
Salman Beigi,
Andrew Drucker,
Bill Fefferman,
Peter W. Shor:
The Power of Unentanglement.
Electronic Colloquium on Computational Complexity (ECCC) 15(051): (2008) |
| 52 | EE | Scott Aaronson:
On Perfect Completeness for QMA.
Electronic Colloquium on Computational Complexity (ECCC) 15(067): (2008) |
| 51 | EE | Scott Aaronson,
John Watrous:
Closed Timelike Curves Make Quantum and Classical Computing Equivalent.
Electronic Colloquium on Computational Complexity (ECCC) 15(092): (2008) |
| 50 | EE | Scott Aaronson:
Quantum certificate complexity.
J. Comput. Syst. Sci. 74(3): 313-322 (2008) |
| 2007 |
|---|
| 49 | EE | Scott Aaronson:
The Limits of Quantum Computers.
CSR 2007: 4 |
| 48 | EE | Scott Aaronson,
Greg Kuperberg:
Quantum versus Classical Proofs and Advice.
IEEE Conference on Computational Complexity 2007: 115-128 |
| 47 | EE | Scott Aaronson:
Review of "The Access Principle by John Willinsky, " MIT Press, 2005.
SIGACT News 38(4): 19-23 (2007) |
| 46 | EE | Scott Aaronson,
Greg Kuperberg:
Quantum Versus Classical Proofs and Advice.
Theory of Computing 3(1): 129-157 (2007) |
| 2006 |
|---|
| 45 | EE | Scott Aaronson:
QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols.
IEEE Conference on Computational Complexity 2006: 261-273 |
| 44 | EE | Scott Aaronson:
Oracles Are Subtle But Not Malicious.
IEEE Conference on Computational Complexity 2006: 340-354 |
| 43 | EE | Scott Aaronson,
Greg Kuperberg:
Quantum Versus Classical Proofs and Advice
CoRR abs/quant-ph/0604056: (2006) |
| 42 | EE | Scott Aaronson,
Greg Kuperberg:
Quantum Versus Classical Proofs and Advice.
Electronic Colloquium on Computational Complexity (ECCC) 13(055): (2006) |
| 41 | EE | Scott Aaronson:
The Learnability of Quantum States.
Electronic Colloquium on Computational Complexity (ECCC) 13(106): (2006) |
| 40 | EE | Scott Aaronson:
Lower Bounds for Local Search by Quantum Arguments.
SIAM J. Comput. 35(4): 804-824 (2006) |
| 2005 |
|---|
| 39 | EE | Scott Aaronson:
The complexity of agreement.
STOC 2005: 634-643 |
| 38 | EE | Scott Aaronson:
Oracles Are Subtle But Not Malicious
CoRR abs/cs/0504048: (2005) |
| 37 | EE | Scott Aaronson:
NP-complete Problems and Physical Reality
CoRR abs/quant-ph/0502072: (2005) |
| 36 | EE | Scott Aaronson:
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
CoRR abs/quant-ph/0510230: (2005) |
| 35 | EE | Scott Aaronson:
Quantum Computing, Postselection, and Probabilistic Polynomial-Time
Electronic Colloquium on Computational Complexity (ECCC)(003): (2005) |
| 34 | EE | Scott Aaronson:
NP-complete Problems and Physical Reality
Electronic Colloquium on Computational Complexity (ECCC)(026): (2005) |
| 33 | EE | Scott Aaronson:
Oracles Are Subtle But Not Malicious
Electronic Colloquium on Computational Complexity (ECCC)(040): (2005) |
| 32 | EE | Scott Aaronson:
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
Electronic Colloquium on Computational Complexity (ECCC)(129): (2005) |
| 31 | EE | Scott Aaronson:
Guest Column: NP-complete problems and physical reality.
SIGACT News 36(1): 30-52 (2005) |
| 30 | EE | Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication.
Theory of Computing 1(1): 1-28 (2005) |
| 29 | EE | Scott Aaronson,
Andris Ambainis:
Quantum Search of Spatial Regions.
Theory of Computing 1(1): 47-79 (2005) |
| 2004 |
|---|
| 28 | EE | Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication.
IEEE Conference on Computational Complexity 2004: 320-332 |
| 27 | EE | Scott Aaronson:
Multilinear formulas and skepticism of quantum computing.
STOC 2004: 118-127 |
| 26 | EE | Scott Aaronson:
Lower bounds for local search by quantum arguments.
STOC 2004: 465-474 |
| 25 | EE | Scott Aaronson:
Limits on Efficient Computation in the Physical World
CoRR abs/quant-ph/0412143: (2004) |
| 24 | EE | Scott Aaronson:
Quantum Computing, Postselection, and Probabilistic Polynomial-Time
CoRR abs/quant-ph/0412187: (2004) |
| 23 | EE | Scott Aaronson:
The Complexity of Agreement
CoRR cs.CC/0406061: (2004) |
| 22 | EE | Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication
CoRR quant-ph/0402095: (2004) |
| 21 | EE | Scott Aaronson,
Daniel Gottesman:
Improved Simulation of Stabilizer Circuits
CoRR quant-ph/0406196: (2004) |
| 20 | EE | Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication
Electronic Colloquium on Computational Complexity (ECCC)(026): (2004) |
| 19 | EE | Scott Aaronson:
The Complexity of Agreement
Electronic Colloquium on Computational Complexity (ECCC)(061): (2004) |
| 18 | EE | Scott Aaronson,
Yaoyun Shi:
Quantum lower bounds for the collision and the element distinctness problems.
J. ACM 51(4): 595-605 (2004) |
| 2003 |
|---|
| 17 | EE | Scott Aaronson,
Andris Ambainis:
Quantum Search of Spatial Regions.
FOCS 2003: 200-209 |
| 16 | EE | Scott Aaronson:
Quantum Certificate Complexity.
IEEE Conference on Computational Complexity 2003: 171-178 |
| 15 | | Scott Aaronson:
Is P Versus NP Formally Independent?
Bulletin of the EATCS 81: 109-136 (2003) |
| 14 | EE | Scott Aaronson:
Lower Bounds for Local Search by Quantum Arguments
CoRR quant-ph/0307149: (2003) |
| 13 | EE | Scott Aaronson:
Multilinear Formulas and Skepticism of Quantum Computing
CoRR quant-ph/0311039: (2003) |
| 12 | EE | Scott Aaronson:
Quantum Certificate Complexity
Electronic Colloquium on Computational Complexity (ECCC) 10(005): (2003) |
| 11 | EE | Scott Aaronson:
Lower Bounds for Local Search by Quantum Arguments
Electronic Colloquium on Computational Complexity (ECCC)(057): (2003) |
| 10 | EE | Scott Aaronson:
Multilinear Formulas and Skepticism of Quantum Computing
Electronic Colloquium on Computational Complexity (ECCC)(079): (2003) |
| 9 | EE | Scott Aaronson:
Algorithms for Boolean Function Query Properties.
SIAM J. Comput. 32(5): 1140-1157 (2003) |
| 2002 |
|---|
| 8 | EE | Scott Aaronson:
Quantum lower bound for the collision problem.
STOC 2002: 635-642 |
| 7 | EE | Scott Aaronson:
Quantum Lower Bound for Recursive Fourier Sampling
CoRR quant-ph/0209060: (2002) |
| 6 | EE | Scott Aaronson:
Quantum Certificate Complexity
CoRR quant-ph/0210020: (2002) |
| 5 | EE | Scott Aaronson:
Quantum Lower Bound for Recursive Fourier Sampling
Electronic Colloquium on Computational Complexity (ECCC)(072): (2002) |
| 2001 |
|---|
| 4 | EE | Scott Aaronson:
Algorithms for Boolean Function Query Properties
CoRR cs.CC/0107010: (2001) |
| 3 | EE | Scott Aaronson:
Quantum Lower Bound for the Collision Problem
CoRR quant-ph/0111102: (2001) |
| 2000 |
|---|
| 2 | EE | Scott Aaronson:
Query Complexity: Worst-Case Quantum Versus Average-Case Classical
CoRR cs.CC/0001013: (2000) |
| 1997 |
|---|
| 1 | EE | Scott Aaronson:
Optimal Demand-oriented Topology for Hypertext Systems.
SIGIR 1997: 168-177 |
