#

### 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

Japan

*May 6, 2011*
##### 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, Article 4
2011 Article 2

Special Issue
Published articles