  We prove that the height of any algebraic computation tree for deciding
membership in a semialgebraic set is bounded from below (up to a multiplicative
constant) by the logarithm of m-th Betti number (with respect to singular
homology) of the set, divided by m+1. This result complements the well known
lower bound by Yao for locally closed semialgebraic sets in terms of the total
Borel-Moore Betti number. We also prove that the height is bounded from below
by the logarithm of m-th Betti number of a projection of the set onto a
coordinate subspace, divided by (m+1)^2. We illustrate these general results by
examples of lower complexity bounds for some specific computational problems.
