# Optimization of Polynomials on the Unit Sphere

Tuesday, January 16, 2007 - 2:00pm - 2:50pm

EE/CS 3-180

Alexander Barvinok (University of Michigan)

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

focused: the ratio of their maximum absolute value and the L

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

focused: the ratio of their maximum absolute value and the L

^{2}norm is large.MSC Code:

30C80

Keywords: