Large Structures Seminar: Nicolai Vorobjov

We prove that the height of any algebraic computation tree for deciding membership in a semialgebraic set $Σ ⊂ R^n$ is bounded from below by

$$\frac{c_1 \cdot log(b_m(Σ))}{(m + 1)}− c_2\cdot n,$$

where $b_m(Σ)$ is the m-th Betti number of $Σ$ with respect to “ordinary” (singular) homology, and $c_1$, $c_2$ are some (absolute) positive constants. 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 if $ρ : R^n → R^{n-r}$ is the projection map, then the hight of any tree deciding membership in $Σ$ is bounded from below by

$$\frac{c_1\cdot log(b_m(ρ(Σ))}{(m + 1)^2}-\frac{c_2\cdot n}{m+1}$$

for some positive constants $c_1$, $c_2$.

We illustrate these general results by examples of lower complexity bounds for some specific computational problems.

An analogous theory is developed for arithmetic networks, a computational model aimed to capture the idea of a parallel computation in its simplest form.

Here we generalize lower bounds of Montana, Morais and Pardo (who considered locally closed semialgebraic sets relative to Borel-Moore homology) to arbitrary semialgebraic sets relative to singular homology.