Institut für Informatik   Abteilung V

 Universität Bonn -> Institut für Informatik -> Abteilung V CS-Reports 1995 Copyright 1995 Universität Bonn, Institut für Informatik, Abt. V 85144 A Lower Bound for Randomized Algebraic Decision Trees Dima Grigoriev, Marek Karpinski, Friedhelm Meyer auf der Heide, Roman Smolensky [Download PostScript] [Download PDF] 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. As an application, among other things, we derive, for the first time, $\Omega(n^2)$ randomized lower bound for the {\em knapsack problem} (which was previously only known for deterministic algebraic decision trees). Last Change: 11/05/14 at 09:54:28  English Universität Bonn -> Institut für Informatik -> Abteilung V