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 coefficients
Authors: Peter Bürgisser 1; Christian Ikenmeyer 1
NULL##NULL
Peter Bürgisser;Christian Ikenmeyer
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 $S_n$. 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 $\mathrm{KRONCOEFF}$ of computing Kronecker coefficients is very difficult. More specifically, we prove that $\mathrm{KRONCOEFF}$ is #$\mathrm{P}$-hard and contained in the complexity class $\mathrm{GapP}$. Formally, this means that the existence of a polynomial time algorithm for $\mathrm{KRONCOEFF}$ is equivalent to the existence of a polynomial time algorithm for evaluating permanents.
Adve, Anshul; Robichaux, Colleen; Yong, Alexander, 2019, Vanishing Of LittlewoodâRichardson Polynomials Is In P, Computational Complexity, 28, 2, pp. 241-257, 10.1007/s00037-019-00183-6.
Luo, Sammy; Sellke, Mark, 2016, The Saxl Conjecture For Fourth Powers Via The Semigroup Property, Journal Of Algebraic Combinatorics, 45, 1, pp. 33-80, 10.1007/s10801-016-0700-z.