  Our first contribution in this paper is to prove that three natural sum of
squares (sos) based sufficient conditions for convexity of polynomials, via the
definition of convexity, its first order characterization, and its second order
characterization, are equivalent. These three equivalent algebraic conditions,
henceforth referred to as sos-convexity, can be checked by semidefinite
programming whereas deciding convexity is NP-hard. If we denote the set of
convex and sos-convex polynomials in $n$ variables of degree $d$ with
$\tilde{C}_{n,d}$ and $\tilde{\Sigma C}_{n,d}$ respectively, then our main
contribution is to prove that $\tilde{C}_{n,d}=\tilde{\Sigma C}_{n,d}$ if and
only if $n=1$ or $d=2$ or $(n,d)=(2,4)$. We also present a complete
characterization for forms (homogeneous polynomials) except for the case
$(n,d)=(3,4)$ which is joint work with G. Blekherman and is to be published
elsewhere. Our result states that the set $C_{n,d}$ of convex forms in $n$
variables of degree $d$ equals the set $\Sigma C_{n,d}$ of sos-convex forms if
and only if $n=2$ or $d=2$ or $(n,d)=(3,4)$. To prove these results, we present
in particular explicit examples of polynomials in
$\tilde{C}_{2,6}\setminus\tilde{\Sigma C}_{2,6}$ and
$\tilde{C}_{3,4}\setminus\tilde{\Sigma C}_{3,4}$ and forms in
$C_{3,6}\setminus\Sigma C_{3,6}$ and $C_{4,4}\setminus\Sigma C_{4,4}$, and a
general procedure for constructing forms in $C_{n,d+2}\setminus\Sigma
C_{n,d+2}$ from nonnegative but not sos forms in $n$ variables and degree $d$.
Although for disparate reasons, the remarkable outcome is that convex
polynomials (resp. forms) are sos-convex exactly in cases where nonnegative
polynomials (resp. forms) are sums of squares, as characterized by Hilbert.
