Lower bound on testing membership to a polyhedron by algebraic decision and computation trees

We introduce a new method of proving lower bounds on the depth of algebraic d-degree decision (or computation) trees and apply it to prove a lower bound Ω(log N) (or Ω(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) (or N > n^Ω(n)). This bound apparently does not follow from the methods developed by Ben-Or, Björner, Lovasz, and Yao because topological invariants used in these methods become trivial for convex polyhedra.