26 citations · 42 across the 14 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2015
Topological lower bounds for arithmetic networks
Andrei Gabrielov, Nicolai Vorobjov
We prove a complexity lower bound on deciding membership in a semialgebraic set for arithmetic networks in terms of the sum of Betti numbers with respect to "ordinary" (singular) h…
cs.CC2015
On topological lower bounds for algebraic computation trees
Nicolai Vorobjov, Andrei Gabrielov
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 o…