Department of Computer Science
 
Chair V

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