Institut für Informatik
 
Abteilung V

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

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

We introduce a new method of proving lower bounds on the depth of algebraic $d$-degree decision trees and apply it to prove a lower bound $\Omega (\log N)$ for testing membership to an $n$-dimensional convex polyhedron having $N$ faces of all dimensions, provided that $N> (nd)^{\Omega (n)}$. This bound apparently does not follow from the methods developed by M. Ben-Or, A. Bj\"orner, L. Lovasz, and A. Yao [B. 83], [BLY 93], [Y 94] because topological invariants used in these methods become trivial for convex polyhedra.

Last Change: 08/25/04 at 08:40:33
 English
Universität Bonn -> Institut für Informatik -> Abteilung V