|
Universität Bonn -> Institut für Informatik -> Abteilung V | ||
CS-APX-Reports 1996 | Copyright 1996 Universität Bonn, Institut für Informatik, Abt. V | |
8931
|
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 |