Randomization and the Computational Power of Analytic and Algebraic Decision Trees
Dima Grigoriev, Marek Karpinski, Roman Smolensky · 1997
We introduce a new powerful method for proving lower bounds on randomized and deterministic analytic decision trees, and give direct applications of our results towards some concrete geometric problems. We design also randomized algebraic decision trees for recognizing the positive octant in R n or computing MAX in R n+1 in depth log 0(1) n. Both problems are known to have linear lower lower bounds for the depth of any deterministic analytic decision tree recognizing them. The main new (and unifying) 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 leading terms at the specially chosen points. This allows us to reduce the complexity of a decision tree to the complexity of a certain boolean circuit. Dept. of Computer Science and Mathematics, Penn State University, University Park, PA 16802. Supported in part by NSF grant CCR-9424358. E-mail: [email protected] y Dept. of Computer Science, Universi...