Name
Abstract | ||
|---|---|---|
We exhibit a new method for showing lower bounds for time-space tradeoffs of polynomial evaluation procedures given by straight-line programs. From the 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 space, denoted by S , is measured by the maximal number of pebbles (registers) used during the given evaluation procedure. The time-space tradeoff function considered in this paper is LS 2 . We show that for “almost all” univariate polynomials of degree at most d our time-space tradeoff functions satisfy the inequality LS 2 ⩾ d 8 . From this we conclude that for “almost all” degree d univariate polynomials, any nonscalar time optimal evaluation procedure requires space at least S ⩾ c 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 tradeoff (this means that our tradeoff function increases linearly in the degree). |
Year | DOI | Venue |
|---|---|---|
2000 | 10.1006/jcom.1999.0526 | J. Complexity |
Keywords | DocType | Volume |
time-space tradeoff,straight-line program,algebraic complexity theory,Time-space tradeoffs,elimination theory,pebble game | Journal | 16 |
Issue | ISSN | Citations |
1 | Journal of Complexity | 6 |
PageRank | References | Authors |
0.60 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| M. Aldaz | 1 | 7 | 0.98 |
| J. Heintz | 2 | 162 | 19.20 |
| G. Matera | 3 | 16 | 2.91 |
| J. L. Montaña | 4 | 10 | 1.43 |
| L. M. Pardo | 5 | 72 | 6.82 |