Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
| |
|
Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
D. Grigoriev1  , M. Karpinski2, 3 and N. Vorobjov4
| (1) |
Departments of Computer Science and Mathematics, Perm State University, 16802 University Park, PA, USA |
| (2) |
Department of Computer Science, University of Bonn, 53117 Bonn, Germany |
| (3) |
International Computer Science Institute, 94704 Berkeley, CA, USA |
| (4) |
School of Mathematical Sciences, University of Bath, Avon BA2 7AY, Bath, England |
Received: 27 December 1994 Revised: 15 April 1996
Abstract We introduce a new method of proving lower bounds on the depth of algebraic d-degree decision (resp. computation) trees and apply it to prove a lower bound Ω (log N) (resp. Ω (log N/log log N)) for testing membership to an n-dimensional convex polyhedron having N faces of all dimensions, provided that N > ( nd) Ω(n) (resp. N > n Ω(n)). This bound apparently does not follow from the methods developed by Ben-Or, Björner, Lovasz, and Yao [1], [4], [24] because
topological invariants used in these methods become trivial for convex polyhedra
The research of D. Grigoriev was supported in part by NSF Grant CCR-9424358. M. Karpinski was supported in part by DFG Grant
KA673/4-1, by the ESPRIT BR Grants 7097 and EC-US 030, and by the Volkswagen-Stiftung.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|