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
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
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
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
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
by Mark Bun, Robin Kothari, and Justin Thaler
Vol 14, Article 5 (pp 1-27)
Randomized Query Complexity of Sabotaged and Composed Functions
by Shalev Ben-David and Robin Kothari
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Quantum Lower Bound for the Collision Problem with Small Range
by Samuel Kutin