TU Berlin

Fachgebiet Algorithmische AlgebraDr. Christian Ikenmeyer

Inhalt des Dokuments

zur Navigation

Ehemalige Mitarbeiter

Dr. Christian Ikenmeyer

Lupe

Kontakt
University of Liverpool
Department of Computer Science
Ashton Building, Office 311
Ashton Street, Liverpool, L69 3BX
United Kingdom
 
Persönliche Homepage
http://pcwww.liv.ac.uk/~iken/

Publikationen in der Arbeitsgruppe

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

Navigation

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe