The University of Michigan Combinatorics Seminar
Winter 2002
February 15, 4:10-5:00, 3866 East Hall

Estimating the maximum by moments for functions on orbits

Alexander Barvinok

University of Michigan


Let G be a compact group acting in a real vector space V. I will describe a family of inequalities relating the L-infinity norm of a matrix element of the representation of G with its Lp norm for p less than infinity. The results are applied to obtain approximation algorithms to find the maximum absolute value of a given multivariate polynomial over the unit sphere (in which case G is the orthogonal group) and for the multidimensional assignment problem, a hard problem of combinatorial optimization (in which case G is the symmetric group).