Articles under category:
Query Complexity
Query Complexity
|
Vol 20, Article 7 (pp 1-62)
Lower Bound Techniques in the Comparison-Query Model and Applications to Inversion Minimization by Ivan Hu, Dieter van Melkebeek, and Andrew Morgan |
|
Vol 19, Article 11 (pp 1-14)
A Strong XOR Lemma for Randomized Query Complexity by Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn, and Hariharan Srinivasulu |
|
Vol 19, Article 9 (pp 1-35)
Optimal Composition Theorem for Randomized Query Complexity by Dmytro Gavinsky, Troy Lee, Miklos Santha, and Swagato Sanyal |
|
Vol 16, Article 10 (pp 1-71)
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials by Mark Bun, Robin Kothari, and Justin Thaler |
|
Vol 14, Article 15 (pp 1-24)
Quantum-Walk Speedup of Backtracking Algorithms by Ashley Montanaro |
|
Vol 14, Article 5 (pp 1-27)
Randomized Query Complexity of Sabotaged and Composed Functions by Shalev Ben-David and Robin Kothari |
|
Vol 12, Article 18 (pp 1-35)
Upper Bounds on Quantum Query Complexity Inspired by the Elitzur--Vaidman Bomb Tester by Cedric Yen-Yu Lin and Han-Hsuan Lin |
|
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 |