  We give new rounding schemes for SDP relaxations for the problems of
maximizing cubic polynomials over the unit sphere and the $n$-dimensional
hypercube. In both cases, the resulting algorithms yield a $O(\sqrt{n/k})$
multiplicative approximation in $2^{O(k)} \text{poly}(n)$ time. In particular,
we obtain a $O(\sqrt{n/\log n})$ approximation in polynomial time. For the unit
sphere, this improves on the rounding algorithms of Bhattiprolu et. al.
[BGG+17] that need quasi-polynomial time to obtain a similar approximation
guarantee. Over the $n$-dimensional hypercube, our results match the guarantee
of a search algorithm of Khot and Naor [KN08] that obtains a similar
approximation ratio via techniques from convex geometry. Unlike their method,
our algorithm obtains an upper bound on the integrality gap of SDP relaxations
for the problem and as a result, also yields a certificate on the optimum value
of the input instance. Our results naturally generalize to homogeneous
polynomials of higher degree and imply improved algorithms for approximating
satisfiable instances of Max-3SAT.
  Our main motivation is the stark lack of rounding techniques for SDP
relaxations of higher degree polynomial optimization in sharp contrast to a
rich theory of SDP roundings for the quadratic case. Our rounding algorithms
introduce two new ideas: 1) a new polynomial reweighting based method to round
sum-of-squares relaxations of higher degree polynomial maximization problems,
and 2) a general technique to compress such relaxations down to substantially
smaller SDPs by relying on an explicit construction of certain hitting sets. We
hope that our work will inspire improved rounding algorithms for polynomial
optimization and related problems.
