TU Berlin

Fachgebiet Algorithmische AlgebraPublications

Inhalt des Dokuments

zur Navigation

Search for Publication

Suche nach Publikationen

All Publications

The Complexity of Computing Kronecker Coefficients
Zitatschlüssel BI-The-Complexity-Of-Computing-Kronecker-Coefficients
Autor Peter Bürgisser and Christian Ikenmeyer
Buchtitel FPSAC 2008
Seiten 357-368
Jahr 2008
Adresse Valparaiso-Viña del Mar, Chile
Serie DMTCS proc. AJ
Zusammenfassung 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 KC of computing Kronecker coefficients is very difficult. More specifically, we prove that KC is #P-hard and contained in the complexity class Gap. Formally, this means that the existence of a polynomial time algorithm for KC is equivalent to the existence of a polynomial time algorithm for evaluating permanents.
Link zur Publikation Download Bibtex Eintrag



Schnellnavigation zur Seite über Nummerneingabe