Department of Computer Science
 
Chair V

 
University of Bonn -> Department of Computer Science -> Chair V
CS-Reports 1995 Copyright 1995 University of Bonn, Department of Computer Science, 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
 Deutsch
University of Bonn -> Department of Computer Science -> Chair V