On directional vs. undirectional randomized decision tree complexity for read-once formulas
Kazuyuki Amano · 2010
We investigate the relationship between the direc-tional and the undirectional complexity of read-once Boolean formulas on the randomized decision tree model. It was known that there is a read-once Boolean formula such that an optimal randomized al-gorithm to evaluate it is not directional. This was first pointed out by Saks and Wigderson (1986) and an explicit construction of such a formula was given by Vereshchagin (1998). We conduct a systematic search for a certain class of functions and provide an explicit construction of a read-once Boolean formula f on n variables such that the cost of the optimal directional randomized decision tree for f is Ω(nα) and the cost of the optimal randomized undirectional decision tree for f is O(nβ) with α−β> 0.0101. This is the largest known gap so far.