COMPLEXITY LOWER BOUNDS FOR APPROXIMATION ALGEBRAIC COMPUTATION TREES

FELIPE CUCKER DIMA GRIGORIEV

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