Lower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees

TitleLower Bounds on Testing Membership to a Polyhedron by Algebraic Decision Trees
Publication TypeTechnical Report
Year of Publication1993
AuthorsGrigoriev, D. Yu., Karpinski M., & Vorobjov N.
Other Numbers859
Abstract

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. Bjoerner, L. Lovasz, A. Yao ([B 83], [BLY 92]) because the topological invariants used in these methods become trivial for the convex polyhedra.

URLhttp://www.icsi.berkeley.edu/ftp/global/pub/techreports/1993/tr-93-071.pdf
Bibliographic Notes

ICSI Technical Report TR-93-071

Abbreviated Authors

D. Grigoriev, M. Karpinski, and N. Vorobjov

ICSI Publication Type

Technical Report