Fetching the paper…
Reading the bibliography…
We show that there exists a Boolean function $F$ which observes the following separations among deterministic query complexity $(D(F))$, randomized zero error query complexity $(R_0(F))$ and randomized one-sided error query complexity $(R_1(F))$: $R_1(F) = \widetilde{O}(\sqrt{D(F)})$ and $R_0(F)=\widetilde{O}(D(F))^{3/4}$.
Probabilistic boolean decision trees and the complexity of evaluating game trees
Michael E. Saks and Avi Wigderson · 1986
Earlier work this paper cites.
Generic oracles and oracle classes (extended abstract)
Manuel Blum and Russell Impagliazzo · 1987
Earlier work this paper cites.
One-way functions, robustness, and the non-isomorphism of np-complete sets
Juris Hartmanis and Lane A. Hemachandra · 1987
Earlier work this paper cites.
Query complexity, or why is it difficult to seperate NP a {}^{\mbox{a}} cap co NP a {}^{\mbox{a}} from P a {}^{\mbox{a}} by random oracles a?
Gábor Tardos · 1989
Cited alongside, same era.
CREW prams and decision trees
Noam Nisan · 1991
Cited alongside, same era.
On the monte carlo boolean decision tree complexity of read-once formulae
Miklos Santha · 1991
Cited alongside, same era.
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.
Deterministic communication vs. partition number
Mika Göös, Toniann Pitassi, and Thomas Watson · 2015
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…