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.