A Lower Bound for Randomized Algebraic Decision Trees

TitleA Lower Bound for Randomized Algebraic Decision Trees
Publication TypeTechnical Report
Year of Publication1995
AuthorsGrigoriev DYu., Karpinski M, der Heide FMeyer auf, Smolensky R
Other Numbers1008
KeywordsElement Distinctness Problem, Faces, Hyperplanes, Knapsack Problem, Lower Bounds, 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.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1995/tr-95-068.pdf
Bibliographic Notes

ICSI Technical Report TR-95-068

Abbreviated Authors

D. Grigoriev, M. Karpinski, F. M. auf der Heide, and R. Smolensky

ICSI Publication Type

Technical Report