We consider the problem of computing the maximum absolute value of a real
multivariate polynomial on the unit sphere. We identify a class of polynomials for which
the problem admits a randomized polynomial time approximation algorithm consisting in computing the maximum absolute value of the restriction of the polynomial onto a
random subspace of logarithmic dimension and scaling the result.
The characteristic feature of polynomials admitting such an algorithm is that they are