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

Abstract

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.

• The article: PDF (185,372 bytes)
• Source material: ZIP (50,503 bytes)
• Self citation in BIBTeX (304 bytes)

© 2011 Kazuyuki Amano
Licensed under a Creative Commons Attribution License

2011, Article 4

2011 Article 2

Special Issue

Published articles