Peter Bürgisser ; Christian Ikenmeyer
-
The complexity of computing Kronecker coefficients
dmtcs:3622 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2008,
DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
-
https://doi.org/10.46298/dmtcs.3622
The complexity of computing Kronecker coefficientsConference paper
Authors: Peter Bürgisser 1; Christian Ikenmeyer 1
NULL##NULL
Peter Bürgisser;Christian Ikenmeyer
1 Mathematisches Institut der Universität Paderborn
Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group Sn. 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 KRONCOEFF of computing Kronecker coefficients is very difficult. More specifically, we prove that KRONCOEFF is #P-hard and contained in the complexity class GapP. Formally, this means that the existence of a polynomial time algorithm for KRONCOEFF is equivalent to the existence of a polynomial time algorithm for evaluating permanents.
Mark Sellke, 2022, Covering Irrep(Sn) With tensor products and powers, Mathematische Annalen, 388, 1, pp. 831-865, 10.1007/s00208-022-02532-3.
Robert de Mello Koch;Yang-Hui He;Garreth Kemp;Sanjaye Ramgoolam, 2022, Integrality, duality and finiteness in combinatoric topological strings, Journal of High Energy Physics, 2022, 1, 10.1007/jhep01(2022)071, https://doi.org/10.1007/jhep01(2022)071.
Stephen Melczer, Texts & monographs in symbolic computation/Texts and monographs in symbolic computation, Multivariate Series and Diagonals, pp. 93-141, 2020, 10.1007/978-3-030-67080-1_3.