Estimating L ∞ Norms by L 2k Norms for Functions on Orbits

Abstract. Let G be a compact group acting in a real vector space V . We obtain a number of inequalities relating the L ^∞ norm of a matrix element of the representation of G with its L ^2k norm for a positive integer k . As an application, we 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 assignment problem of degree d , a hard problem of combinatorial optimization generalizing the quadratic assignment problem (in which case G is the symmetric group).