@inproceedings{BI-The-Complexity-Of-Computing-Kronecker-Coefficients,
Title = {The Complexity of Computing Kronecker Coefficients},
Author = {Peter Bürgisser and Christian Ikenmeyer},
Booktitle = {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.},
Url = {http://www3.math.tu-berlin.de/algebra/work/kronhard_revision.pdf},
Reviewed = {True}
}