Chicago Journal of Theoretical Computer Science

CJTCS Special Issue: CATS 2010

Selected papers from

2010 Computing: The Australasian Theory Symposium

held in Brisbane, Australia, January 18-21 2010.

Guest Editors: Taso Viglas, University of Sydney, Australia

Alex Potanin, Victoria University, Wellington, NZ

Article 2011-3

Published by the Department of Computer Science, The University of Chicago.

On Directional vs. General Randomized Decision Tree Complexity for Read-Once Formulas

Kazuyuki Amano
Department of COmputer Science
Gunma University
Tenjin-cho 1-5-1, Kiryu, Gunma 376-8515
May 6, 2011

We investigate the relationship between the complexities of two models of randomized decision trees for read-once Boolean functions; namely, with the directional restriction and without it. A decision tree is directional if it reads a variable in a sub-formula, then it has to evaluate the sub-formula completely before reading another variable that appears in a different sub-formula. It was known that there is a read-once Boolean formula such that an optimal randomized decision tree to evaluate it is not directional. This was first pointed out by Saks and Wigderson [FOCS '86] and an explicit construction of such a formula was given by Vereshchagin [TCS '98]. In this paper, 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 BigOmega(n^alpha) and the cost of the optimal randomized decision tree (without the directional restriction) for f is O(n^beta) with alpha-beta>0.0101. This is the largest known gap so far.

DOI: 10.4086/cjtcs.2011.003

[] 2011, Article 4 [] 2011 Article 2
[back] Special Issue [back] Published articles
[CJCTS home]