We investigate the deterministic and the randomized decision tree complexities of Boolean functions, denoted by D(f) and R(f), respectively. A long standing conjecture is that, for every Boolean) function f, R(f) =
In the Boolean decision tree model there is at least a linear gap between the Monte Carlo and the Las Vegas complexity of a function depending on the error probability. The author proves for a large class of read-once formulae that this trivial speed-up is the best that a Monte Carlo algorithm can achieve. For every formula F belonging to that class it is shown that the Monte Carlo complexity of F with two-sided error p is (1-2p)R(F), and with one-sided error p is (1-p)R(F), where R(F) denotes the Las Vegas complexity of F. The result follows from a general lower bound that is derived on the Monte Carlo complexity of these formulae.>
We show that there exists a Boolean function F which gives 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) = ~O(sqrt{D(F)) and R_0(F)=~O(D(F))^3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R_0(f)=Omega(D(f))^0.753.. . This also shows widest separation between R_1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous non-deterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R_0(f), and polynomial separation between R_0(f) and R_1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.
We show that there exists a Boolean function F which gives the following separations among deterministic query complexity (D(F)), randomized zero error query complexity (R0(F)) and randomized one-sided error query complexity (R1(F)): R1(F) = Õ( √ D(F)) and R0(F) = Õ(D(F))3/4. This refutes the conjecture made by Saks and Wigderson that for any Boolean function f, R0(f) = Ω(D(f))0.753.. This also shows widest separation between R1(f) and D(f) for any Boolean function. The function F was defined by Göös, Pitassi and Watson who studied it for showing a separation between deterministic decision tree complexity and unambiguous nondeterministic decision tree complexity. Independently of us, Ambainis et al proved that different variants of the function F certify optimal (quadratic) separation between D(f) and R0(f), and polynomial separation between R0(f) and R1(f). Viewed as separation results, our results are subsumed by those of Ambainis et al. However, while the functions considered in the work of Ambainis et al are different variants of F, in this work we show that the original function F itself is sufficient to refute the Saks-Wigderson conjecture and obtain widest possible separation between the deterministic and one-sided error randomized query complexity.
Saks and Wigderson [in Proceedings of the 27th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986, pp. 29--38] conjectured that R0(f)=Ω(D(f)0.753…) for all Boolean functions f, where R0 denotes the randomized zero-error query complexity and D denotes the deterministic query complexity. We show that for the pointer function GPWr×s defined by Göös, Pitassi, and Watson [in Proceedings of the 56th FOCS, IEEE, Piscataway, NJ, 2015, pp. 1077--1088], the following hold: (a) R1(GPWr×s)=Θ(r+s) and (b) R1(GPWr×s)=Θ(r+rs), where R1 denotes the randomized one-sided error query complexity. These results imply that (i) R0(GPWs2×s)=O(D(GPWs2×s)2/3), thereby refuting the conjecture of Saks and Wigderson, and (ii) R1(GPWs×s)=O(R0(GPWs×s)2/3), thereby providing a polynomial separation between the randomized zero-error and one-sided error query complexity measures.