Complexity Lower Bounds for Approximation Algebraic Computation Trees

Felipe Cucker and Dima Grigoriev

We prove lower bounds for approximate computations of piecewise polynomial functions which, in particular, apply for round-off computations of such functions.