Explicit polynomials in 1 variable with superlogarithmic circuit complexity lower bounds? By counting arguments, one can show that there exist polynomials of degree n in 1 variable (i.e., something of the form $a_n x^n + a_{n-1} x^{n-1} + \cdots + a_0)$ which have circuit complexity n.  Also, one can show that a polynomial like $x^n$ requires at least $\log_2 n$ multiplications (you need that just to get a high enough degree).  Are there any explicit examples of polynomials in 1 variable with a superlogarithmic lower bound on complexity? (results over any field would be interesting)
Paterson and Stockmeyer show that for most $n$-tuples of rational numbers $(a_1, \dotsc, a_n)$, evaluating $\prod_{i=1}^{n} (x - a_i)$ requires $\Omega(\sqrt{n})$ arithmetic operations, and this is tight.

The following polynomials get within a logarithmic factor of the $\sqrt{n}$ bound, by results of Strassen, Schnorr, and Heintz &amp; Sieveking: $\sum_{i=1}^{n} 2^{2^{i}} x^{i}$, $\sum_{i=1}^{n} e^{2 \pi i / 2^{i}} x^{i}$, $\sum_{i=1}^{n} i^{r} x^{i}$ (for $r$ a rational that is not an integer), etc.  For exact references and for more on this, see pp. 324-325 of von zur Gathen's survey.