Rheinische Friedrich-Wilhelms-Universität Bonn Institut für Informatik
 
Abteilung V

 
Universität Bonn -> Institut für Informatik -> Abteilung V
CS-Reports 1993 Copyright 1993 Universität Bonn, Institut für Informatik, Abt. V
85103

Lower Bounds on Testing Membership to Polyhedron by Algebraic Decision Trees
Dima Grigoriev, Marek Karpinski, Nicolai Vorobjov
[Download PostScript] [Download PDF]

We describe a new method of proving lower bounds on the depth of algebraic decision trees and apply it to prove a lower bound $\Omega (\log N)$ for testing membership to a convex polyhedron having $N$ facets of all dimensions. This bound apparently does not follow from the methods developed by M. Ben-Or, A. Björner, L. Lovasz, A. Yao ([B 83], [BLY 92]) because the topological invariants used in these methods become trivial for the convex polyhedra.

Last Change: 09/01/04 at 08:15:57
 English
Universität Bonn -> Institut für Informatik -> Abteilung V

Powered by Zope