# The complexity of computing Kronecker coefficients

Abstract : 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.
Keywords :
Document type :
Conference papers
Domain :
Complete list of metadata

Cited literature [19 references]

https://hal.inria.fr/hal-01185157
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 19, 2015 - 11:42:29 AM
Last modification on : Thursday, May 11, 2017 - 1:02:52 AM
Long-term archiving on: : Friday, November 20, 2015 - 10:32:43 AM

### File

dmAJ0131.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01185157, version 1

### Citation

Peter Bürgisser, Christian Ikenmeyer. The complexity of computing Kronecker coefficients. 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), 2008, Viña del Mar, Chile. pp.357-368. ⟨hal-01185157⟩

Record views