Randomized vs. Deterministic Decision Tree Complexity for Read-Once
R. Heiman, Weizmann Inst, Avi Wigderson · 1991
We consider the deterministic and the randomized decision tree complexities for Boolean functions, denoted DC(f) and RC(f), respectively. It is well known that RC(f) 2 DC(f)0.5 for every Boolean function f (called ‘0.5-exponent’), but no better lower bound is known for all Boolean functions whereas the best known up per bound is RC(f) = e(DC(f)0.753-.) (or ‘0.753 ...exponent’) for some Boolean function f. Our result is a 0.51 lower bound on the exponent for all read-once functions, functions representable by formulae in which each input variable appears exactly once. To obtain it we generalize an existing lower bound technique [SWSS] and combine it with restrictions arguments. This result provides a lower bound of on the number of positions that have to be evaluated by any randomized cr-p pruning algorithm computing the value of any two-person zero-sum game tree with n final positions.