Fetching the paper…
Reading the bibliography…
We show a power 2.5 separation between bounded-error randomized and quantum query complexity for a total Boolean function, refuting the widely believed conjecture that the best such separation could only be quadratic (from Grover's algorithm).
Probabilistic Boolean decision trees and the complexity of evaluating game trees
Michael Saks and Avi Wigderson · 1986
Earlier work this paper cites.
CREW PRAMs and decision trees
Noam Nisan · 1991
Earlier work this paper cites.
Rapid solution of problems by quantum computation
David Deutsch and Richard Jozsa · 1992
Earlier work this paper cites.
On the degree of Boolean functions as real polynomials
Noam Nisan and Mario Szegedy · 1995
Earlier work this paper cites.
On rank vs. communication complexity
Noam Nisan and Avi Wigderson · 1995
Earlier work this paper cites.
On the Monte Carlo Boolean decision tree complexity of read-once formulae
Miklos Santha · 1995
Earlier work this paper cites.
A fast quantum mechanical algorithm for database search
Lov K. Grover · 1996
Earlier work this paper cites.
Strengths and weaknesses of quantum computing
Charles H. Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani · 1997
Earlier work this paper cites.
Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer
Peter W. Shor · 1997
Earlier work this paper cites.
On the power of quantum computation
Daniel R. Simon · 1997
Earlier work this paper cites.
Quantum algorithms revisited
Richard Cleve, Artur Ekert, Chiara Macchiavello, and Michele Mosca · 1998
Earlier work this paper cites.
Quantum lower bounds by polynomials
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf · 2001
Earlier work this paper cites.
Complexity measures and decision tree complexity: a survey
Harry Buhrman and Ronald de Wolf · 2002
Earlier work this paper cites.
Quantum amplitude amplification and estimation
Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp · 2002
Earlier work this paper cites.
Polynomial degree vs. quantum query complexity
Andris Ambainis · 2003
Cited alongside, same era.
Quantum search on bounded-error inputs
Peter Høyer, Michele Mosca, and Ronald de Wolf · 2003
Cited alongside, same era.
Quantum lower bounds for the collision and the element distinctness problems
Scott Aaronson and Yaoyun Shi · 2004
Cited alongside, same era.
Exact quantum query complexity for total Boolean functions
Gatis Midrijanis · 2004
Cited alongside, same era.
Quantum certificate complexity
Scott Aaronson · 2006
Cited alongside, same era.
Exponential separation of quantum and classical online space complexity
François Le Gall · 2006
Cited alongside, same era.
Superlinear advantage for exact quantum algorithms
Andris Ambainis · 2013
Later among the works it cites.
Adversary lower bound for the k-sum problem
Aleksandrs Belovs and Robert Špalek · 2013
Later among the works it cites.
Composition limits and separating examples for some Boolean function complexity measures
Justin Gilmer, Michael Saks, and Srikanth Srinivasan · 2013
Later among the works it cites.
On fractional block sensitivity
Raghav Kulkarni and Avishay Tal · 2013
Later among the works it cites.
A strong direct product theorem for quantum query complexity
Troy Lee and Jérémie Roland · 2013
Later among the works it cites.
Approximating the AND-OR tree
Alexander A. Sherstov · 2013
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Robert Špalek and Mario Szegedy · 2006
Cited alongside, same era.
Quantum walk algorithm for element distinctness
Andris Ambainis · 2007
Cited alongside, same era.
Robust polynomials and quantum algorithms
Harry Buhrman, Ilan Newman, Hein Rohrig, and Ronald de Wolf · 2007
Cited alongside, same era.
Negative weights make adversaries stronger
Peter Høyer, Troy Lee, and Robert Špalek · 2007
Cited alongside, same era.
The partition bound for classical communication complexity and query complexity
Rahul Jain and Hartmut Klauck · 2010
Cited alongside, same era.
Quantum query complexity of state conversion
Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Špalek, and Mario Szegedy · 2011
Cited alongside, same era.
Avishay Tal · 2013
Later among the works it cites.
How low can approximate degree and quantum query complexity be for total boolean functions?
Andris Ambainis and Ronald de Wolf · 2014
Later among the works it cites.
Forrelation: A problem that optimally separates quantum from classical computing
Scott Aaronson and Andris Ambainis · 2015
Closest in time.
Separations in query complexity based on pointer functions
Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, and Juris Smotrovs · 2015
Closest in time.
Hardness amplification and the approximate degree of constant-depth circuits
Mark Bun and Justin Thaler · 2015
Closest in time.
Randomized communication vs. partition number
Mika Göös, T.S. Jayram, Toniann Pitassi, and Thomas Watson · 2015
Closest in time.
Deterministic communication vs. partition number
Mika Göös, Toniann Pitassi, and Thomas Watson · 2015
Closest in time.