SPARSE INTERPOLATION OF SYMMETRICAL POLYNOMIALS

We develop efficient algorithms for computing the expansion of a given symmetric polynomial into Schur functions. This problem frequently ar ises in applications as the problem of decomposing a given representat ion of the symmetric (or general linear) group into irreducible consti tuents. Our algorithms are probabilistic, and run in time which is pol ynomial in the sizes of the input and output. They can be used to comp ute Littlewood-Richardson coefficients, Kostka numbers, and irreducibl e characters of the symmetric group. (C) 1997 Academic Press.