Fetching the paper…
Reading the bibliography…
In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$.
Probabilistic computations: toward a unified measure of complexity
A. C. Yao · 1977
Earlier work this paper cites.
Lower bounds for probabilistic linear decision trees
M. Snir · 1985
Earlier work this paper cites.
Probabilistic Boolean decision trees and the complexity of evaluating game trees
M. Saks and A. Wigderson · 1986
Earlier work this paper cites.
Generic oracles and oracle classes
M. Blum and R. Impagliazzo · 1987
Earlier work this paper cites.
One-way functions, robustness, and non-isomorphism of NP-complete sets
J. Hartmanis and L. A. Hemachandra · 1987
Earlier work this paper cites.
Query complexity or why is it difficult to separate 𝐍𝐏 A ∩ 𝐜𝐨𝐍𝐏 A \mathbf{NP}^{A}\cap\mathbf{coNP}^{A} from 𝐏 A \mathbf{P}^{A} by a random oracle
G. Tardos · 1990
Earlier work this paper cites.
CREW PRAMs and decision trees
N. Nisan · 1991
Earlier work this paper cites.
Rapid solution of problems by quantum computation
D. Deutsch and R. Jozsa · 1992
Earlier work this paper cites.
On the degree of boolean functions as real polynomials
N. Nisan and M. Szegedy · 1994
Cited alongside, same era.
On the Monte Carlo boolean decision tree complexity of read-once formulae
M. Santha · 1995
Cited alongside, same era.
A fast quantum mechanical algorithm for database search
L. K. Grover · 1996
Cited alongside, same era.
Quantum counting
G. Brassard, P. Høyer, and A. Tapp · 1998
Cited alongside, same era.
Quantum algorithms revisited
R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca · 1998
Cited alongside, same era.
Quantum lower bounds by polynomials
R. Beals, H. Buhrman, R. Cleve, M. Mosca, and R. de Wolf · 2001
Cited alongside, same era.
Quantum amplitude amplification and estimation
Exact quantum query complexity for total boolean functions
G. Midrijānis · 2004
Later among the works it cites.
On randomized and quantum query complexities
G. Midrijānis · 2005
Later among the works it cites.
Superlinear advantage for exact quantum algorithms
A. Ambainis · 2013
Later among the works it cites.
On fractional block sensitivity
R. Kulkarni and A. Tal · 2013
Later among the works it cites.
Forrelation: A problem that optimally separates quantum from classical computing
S. Aaronson and A. Ambainis · 2015
Closest in time.
A super-Grover separation between randomized and quantum query complexities
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
G. Brassard, P. Høyer, M. Mosca, and A. Tapp · 2002
Cited alongside, same era.
Complexity measures and decision tree complexity: a survey
H. Buhrman and R. de Wolf · 2002
Cited alongside, same era.
S. Ben-David · 2015
Closest in time.
Deterministic communication vs. partition number
M. Göös, T. Pitassi, and T. Watson · 2015
Closest in time.
Towards better separation between deterministic and randomized query complexity
S. Mukhopadhyay and S. Sanyal · 2015
Closest in time.