RANDOMIZATION AND THE COMPUTATIONAL POWER OF ANALYTIC AND ALGEBRAIC DECISION TREES

We introduce a new powerful method for proving lower bounds on randomi zed and deterministic analytic decision trees, and give direct applica tions of our results towards some concrete geometric problems. We desi gn also randomized algebraic decision trees for recognizing the positi ve octant in R-n or computing MAX in R-n in depth log(O(1)) n. Both pr oblems are known to have linear lower bounds for the depth of any dete rministic analytic decision tree recognizing them. The main new (and u nifying) proof idea of the paper is in the reduction technique of the signs of testing functions in a decision tree to the signs of their le ading terms at the specially chosen points. This allows us to reduce t he complexity of a decision, tree to the complexity of a certain Boole an circuit.