Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

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

Collections

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⟩

Share

Metrics

Record views

102

Files downloads

931