Service interruption on Monday 11 July from 12:30 to 13:00: all the sites of the CCSD (HAL, EpiSciences, SciencesConf, AureHAL) will be inaccessible (network hardware connection).
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 Connect in order to contact the contributor
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

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, ⟨10.46298/dmtcs.3622⟩. ⟨hal-01185157⟩

Share

Metrics

Record views

77

Files downloads

624