A new method to obtain lower bounds for polynomial evaluation

We present a new method to obtain lower bounds for the time complexity of p olynomial evaluation procedures. Time, denoted by L, is measured in terms o f nonscalar arithmetic operations. In contrast with known methods for provi ng lower complexity bounds, our method is purely combinatorial and does not require powerful tools from algebraic or diophantine geometry. By means of our method we are able to verify the computational hardness of new natural families of univariate polynomials for which this was impossible up to now . By computational hardness we mean that the complexity function L-2 grows linearly in the degree of the polynomials of the family we are considering. Our method can also be applied to classical questions of transcendence pro ofs in number theory and geometry. A list of (old and new) formal power ser ies is given whose transcendence can be shown easily by our method. (C) 200 1 Elsevier Science B.V. All rights reserved.