A New Lower Bound Technique

for Decision Trees 1

by

Rudolf Fleischer 2

ABSTRACT In this paper, we prove two general lower bounds for algebraic decision trees which test membership in a set S ? Rn which is defined by linear inequalities. Let rank(S) be the maximal dimension of a linear subspace contained in the closure of S.

First we prove that any decision tree which uses multilinear functions (i.e. arbitrary products of linear functions) must have depth at least n ? rank(S). This solves an open question raised by A.C. Yao ([Y89]) and can be used to show that multilinear functions are not really more powerful than simple comparisons between the input variables when computing the largest k elements of n given numbers. Yao could only prove this result in the special case when products of at most two linear functions are used. Our proof is based on a dimension argument. It seems to be the first time that such an approach yields good lower bounds for nonlinear decision trees.

Surprisingly, we can use the same methods to give an alternative proof for Rabin's fundamental Theorem ([Rab]), namely that the depth of any decision tree using arbitrary analytic functions is at least n ? rank(S). Since we show that Rabin's original proof is incorrect, our proof of Rabin's Theorem is not only the first correct one but also generalizes the Theorem to a wider class of functions.

1 . Introduction

Among other algebraic complexity measures (e.g. [MST], [ST]), the algebraic decision tree and algebraic computation tree models have have turned out to be very useful in proving lower bounds for elementary combinatorial or geometric problems like maximum finding, set equality, set disjointness and sorting (see [Be] for more examples) or even more complicated problems like convex polygon inclusion ([Ram]) and motion planning ([OD]).

The algebraic decision tree model is an abstraction of "real" algorithms where only comparisons between input variables or functions of input variables are counted whereas all other time-consuming operations like data-management, function evaluation or other control structures have zero cost. For complex problems, this simplification can make the problem considerably easier; for example, the knapsack problem which is known to be NP- complete has a polynomial solution in the decision tree model (e.g. [MadH]). Therefore, lower bounds in the decision tree model can only be tight for quite simple problems.

1 This work was (partially) supported by the ESPRIT Basic Research Action No. 7141 (ALCOM II) 2 Max-Planck-Institut f?ur Informatik, W-6600 Saarbr?ucken, Germany, e-mail: rudolf@mpi-sb.mpg.de