Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1996 Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V 85149 Randomization and the Computational Power of Analytic and Algebraic Decision Trees Dima Grigoriev, Marek Karpinski, Roman Smolensky [Download PostScript] [Download PDF] We introduce a new powerful method for proving {\it lower bounds} on {\it randomized} and {\it deterministic} analytic decision trees, and give direct applications of our results towards some concrete geometric problems. We design also {\it randomized} algebraic decision trees for recognizing the {\it positive octant} in $\run$ or computing MAX in $\R^{n+1}$ in depth $\log^{\bigO{}(1)}n$. Both problems are known to have linear lower bounds for the depth of any deterministic analytic decision tree recognizing them. The main {\em new} (and {\em unifying}) proof idea of the paper is in the reduction technique of the signs of {\em testing} functions in a decision tree to the signs of their {\em leading terms} at the specially chosen points. This allows us to reduce the complexity of a {\em decision} tree to the complexity of a certain {\em boolean} circuit. Last Change: 11/05/14 at 09:59:40  English Universität Bonn -> Institut für Informatik -> Abteilung V