Let $p=\sum_{i=0}^{n}a_ix^i$. Under what conditions on the coefficients $a_i$ is $p$ convex? Strictly convex?

3$\begingroup$ This is about the sign of the second derivative. $\endgroup$ – Charles Matthews Jun 21 '10 at 19:54
p is convex iff p'' is nonnegative. And a polynomial is nonnegative iff it is the modulus of the square of a polynomial with complex coefficients. So p must be of even degree (or of degree 0 or 1).
If we write $p''=q^2$, then we see that p is convex iff there exist complex coefficients $q_0...q_l$, $l \leq n/2$, such that, for all $k$, $$k(k1)\ a_k=\ \ \Sigma_{i,j \ \ s.t.\atop i+j=k2} \quad q_i \bar{q}_j$$
This is not very explicit, but at least this may be used to generate convex polynomials.
To add some more stuff to @coudy's answer. We need to check whether $p''$ is nonnegative. To that end let us recall some basic results (copied from another MO answer of mine), discussed in these lecture notes; these results are helpful for checking if a univariate polynomial is nonnegative.
Theorem A univariate polynomial is nonnegative if and only if it is a sum of squares.
Theorem Let $\mathbf{x}=[1,x,x^2,\ldots,x^m]^T$, and let $P(x)$ have degree $2m$. Then, $P(x)$ is nonnegative if and only if there exists a $m+1 \times m+1$ positive semidefinite matrix $Q$ such that $P(x) = \mathbf{x}^TQ\mathbf{x}$.
Let $P(x)=\sum_{i=0}^{2m} p_ix^i$. It can be further shown that the matrix $Q$ must satisfy \begin{equation*} p_i = \sum_{j+k=i} Q_{jk},\qquad i=0,1,\ldots,2m. \end{equation*}
Theorem If we can find a positive semidefinite matrix $Q$ that satisfies the above linear constraints (this can be done using regular semidefinite programming software), then the polynomial $P(x)=\sum_{i=0}^{2m} p_ix^i$ is nonnegative or SOS, otherwise not.
@coudy 
If $p''(x) = \sum_{k=2}^{n}k(k1)a_{k}x^{k2}$ and $q(x) = \sum_{l=0}^{(n2)/2}q_{l}x^{l}$, shouldn't we have for $2 \leq k \leq n$ $$k(k1)a_{k} = \sum_{i,j \text{ s.t. } i+j=(k2)} q_{i}\bar{q}_{j}?$$

$\begingroup$ indeed, there was a typo in my answer. This is now corrected, thanks. $\endgroup$ – coudy Sep 22 '12 at 18:53
To add to @coudy's answer: a polynomial is nonnegative if and only if it is a sum of squares, which gives a slightly different set of equations to be satisfied by the second derivative.
p must be of even order, and its leading coefficient must be positive. Moreover, p is strictly convex (convex) if p'' has no real zeros (no real zeros of odd multiplicity). The number of real zeros of a polynomial is characterized by Sturm's theorem (http://en.wikipedia.org/wiki/Sturm's_theorem#Number_of_real_roots).