On the cell probe complexity of polynomial evaluation

AbstractWe consider the cell probe complexity of the polynomial evaluation problem with preprocessing of coefficients, for polynomials of degree at most n over a finite field K. We show that the trivial cell probe algorithm for the problem is optimal if K is sufficiently large compared to n. As an application, we give a new proof of the fact that P ≠ incr-TIME(o(logn/log logn))