Articles under category:
Query Complexity
Vol 11, Article 16 (pp 403-412) [NOTE]
Quantum Algorithm for Monotonicity Testing on the Hypercube
by Aleksandrs Belovs and Eric Blais
Vol 11, Article 12 (pp 299-338) [APRX-RND13 Spec Issue]
Absolutely Sound Testing of Lifted Codes
by Elad Haramaty, Noga Ron-Zewi, and Madhu Sudan
Vol 10, Article 19 (pp 515-533)
Query Complexity Lower Bounds for Reconstruction of Codes
by Sourav Chakraborty, Eldar Fischer, and Arie Matsliah
Vol 10, Article 6 (pp 133-166)
The Need for Structure in Quantum Speedups
by Scott Aaronson and Andris Ambainis
Vol 9, Article 25 (pp 783-807) [APRX-RND12 Spec Issue]
A New Upper Bound on the Query Complexity of Testing Generalized Reed-Muller Codes
by Noga Ron-Zewi and Madhu Sudan
Vol 8, Article 13 (pp 291-319)
Span-Program-Based Quantum Algorithm for Evaluating Formulas
by Ben Reichardt and Robert Špalek
Vol 7, Article 10 (pp 147-153) [NOTE]
The Influence Lower Bound Via Query Elimination
by Rahul Jain and Shengyu Zhang
Vol 5, Article 5 (pp 119-123) [NOTE]
Discrete-Query Quantum Algorithm for NAND Trees
by Andrew M. Childs, Richard Cleve, Stephen P. Jordan, and David Yonge-Mallo
Vol 3, Article 7 (pp 129-157)
Quantum Versus Classical Proofs and Advice
by Scott Aaronson and Greg Kuperberg
Vol 2, Article 9 (pp 173-183)
Tolerant Versus Intolerant Testing for Boolean Properties
by Eldar Fischer and Lance Fortnow
Vol 2, Article 1 (pp 1-18)
All Quantum Adversary Methods are Equivalent
by Robert Špalek and Mario Szegedy
Vol 1, Article 9 (pp 177-216)
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing
by Noga Alon and Asaf Shapira
Vol 1, Article 3 (pp 37-46)
Polynomial Degree and Lower Bounds in Quantum Complexity: Collision and Element Distinctness with Small Range
by Andris Ambainis
Vol 1, Article 2 (pp 29-36)
Quantum Lower Bound for the Collision Problem with Small Range
by Samuel Kutin