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. |
| Cite as: Amano, K. (2010). On Directional vs. Undirectional Randomized Decision Tree Complexity for Read-Once Formulas. In Proc. 16-th Computing: The Australasian Theory Symposium (CATS 2010) Brisbane, Australia. CRPIT, 109. Viglas, T. and Potanin, A. Eds., ACS. 25-30 |
 (from crpit.com)
(local if available)
|