Peter Bürgisser ; Christian Ikenmeyer - The complexity of computing Kronecker coefficients

dmtcs:3622 - Discrete Mathematics & Theoretical Computer Science, January 1, 2008, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) - https://doi.org/10.46298/dmtcs.3622
The complexity of computing Kronecker coefficientsConference paper

Authors: Peter Bürgisser 1; Christian Ikenmeyer 1

  • 1 Mathematisches Institut der Universität Paderborn

Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group Sn. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We show that the problem KRONCOEFF of computing Kronecker coefficients is very difficult. More specifically, we prove that KRONCOEFF is #P-hard and contained in the complexity class GapP. Formally, this means that the existence of a polynomial time algorithm for KRONCOEFF is equivalent to the existence of a polynomial time algorithm for evaluating permanents.


Volume: DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
Section: Proceedings
Published on: January 1, 2008
Imported on: May 10, 2017
Keywords: representations of symmetric groups,tensor products,Kronecker coefficients,computational complexity,[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

6 Documents citing this article

Consultation statistics

This page has been seen 382 times.
This article's PDF has been downloaded 329 times.