DIMACS TR: 96-45

A Lower Bound for Randomized Algebraic Decision Trees

Authors: Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky


We extend the lower bounds on the depth of algebraic decision trees to the case of {\em randomized} algebraic decision trees (with two-sided error) for languages being finite unions of hyperplanes and the intersections of halfspaces, solving a long standing open problem. As an application, among other things, we derive, for the first time, an $\Omega(n^2)$ {\em randomized} lower bound for the {\em Knapsack Problem} which was previously only known for deterministic algebraic decision trees. It is worth noting that for the languages being finite unions of hyperplanes our proof method yields also a new elementary technique for deterministic algebraic decision trees without making use of Milnor's bound on Betti number of algebraic varieties.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-45.ps.gz
DIMACS Home Page