Maximum principle

Tuesday, January 16, 2007 - 2:00pm - 2:50pm
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
Subscribe to RSS - Maximum principle