  In this paper, we study polynomial norms, i.e. norms that are the
$d^{\text{th}}$ root of a degree-$d$ homogeneous polynomial $f$. We first show
that a necessary and sufficient condition for $f^{1/d}$ to be a norm is for $f$
to be strictly convex, or equivalently, convex and positive definite. Though
not all norms come from $d^{\text{th}}$ roots of polynomials, we prove that any
norm can be approximated arbitrarily well by a polynomial norm. We then
investigate the computational problem of testing whether a form gives a
polynomial norm. We show that this problem is strongly NP-hard already when the
degree of the form is 4, but can always be answered by testing feasibility of a
semidefinite program (of possibly large size). We further study the problem of
optimizing over the set of polynomial norms using semidefinite programming. To
do this, we introduce the notion of r-sos-convexity and extend a result of
Reznick on sum of squares representation of positive definite forms to positive
definite biforms. We conclude with some applications of polynomial norms to
statistics and dynamical systems.
