Time-space tradeoffs in algebraic complexity theory

We exhibit a new method for showing lower bounds for time-space tradeoffs o f polynomial evaluation procedures given by straight-line programs. From th e tradeoff results obtained by this method we deduce lower space bounds for polynomial evaluation procedures running in optimal nonscalar time. Time, denoted by L, is measured in terms of nonscalar arithmetic operations and s pace, denoted by S, is measured by the maximal number of pebbles (registers ) used during the given evaluation procedure. The time-space tradeoff funct ion considered in this paper is LS'. We show that for "almost all" univaria te polynomials of degree at most d our time-space tradeoff functions satisf y the inequality LS2 greater than or equal to d/8. From this we conclude th at for "almost all" degree d univariate polynomials, any nonscalar time opt imal evaluation procedure requires space at least S greater than or equal t o c 4 root d where c > 0 is a suitable universal constant. The main part of this paper is devoted to the exhibition of specific families of univariate polynomials which are "hard to compute" in the sense of time-space tradeof f (this means that our tradeoff function increases linearly in the degree). (C) 2000 Academic Press.