Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR95-063 | 19th December 1995 00:00

#### A Lower Bound for Randomized Algebraic Decision Trees

TR95-063
Authors: Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky
Publication: 20th December 1995 19:23
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint