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 L2 norm is large.
MSC Code: