A Lower Bound for Randomized Algebraic Decision Trees

Abstract:

We extend the lower bounds on the depth of algebraic decision trees to the case
of 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)$ randomized lower bound for the 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.