We improve some lower bounds which have been obtained by Strassen and Lipton. In particular there exist polynomials of degree n with 0–1 coefficients that cannot be evaluated with less than
Ö{n/}\sqrt {n/}
(4 log n) nonscalar multiplications/divisions. The evaluation of
p(x) = åd\doteq on e2pi/2d xdp(x) = \sum\limits_{\delta \doteq o}^n {e^{2\pi i/2^\delta } } x^\delta
requires at least n/(12 log n) multiplications/divisions and at least
Ö{n/ (8 log n)}\sqrt {n/ (8 log n)}
nonscalar multiplications/divisions. We specify polynomials with algebraic coefficients that require n/2 multiplications/divisions.