A Lower Bound for Randomized Algebraic Decision Trees
Report ID: TR-527-96Author: Smolensky, Roman / Grigoriev, Dima / Karpinski, Marek / Meyer auf der Heide, Friedhelm
Date: 1996-10-00
Pages: 14
Download Formats: |Postscript|
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.