Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1996 Copyright 1996 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V