direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Search for Publication

Search for publications




All Publications

The Complexity of Computing Kronecker Coefficients
Citation key BI-The-Complexity-Of-Computing-Kronecker-Coefficients
Author Peter Bürgisser and Christian Ikenmeyer
Title of Book FPSAC 2008
Pages 357-368
Year 2008
Address Valparaiso-Viña del Mar, Chile
Series DMTCS proc. AJ
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 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 to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.