Time-space tradeoffs for polynomial evaluation

We develop a new method for showing lower bounds for the time-space tradeof f of polynomial evaluation procedures given by straight-line programs. By m eans of this method we prove an asymptotically sharp lower bound for the ti me-space tradeoff of general procedures of polynomial evaluation and exhibi t specific families of univariate polynomials where this bound is reached. (C) Academie des Sciences/Elsevier, Paris.