direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

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
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

Auxiliary Functions

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