On the complexity of computing Kronecker coefficients
Authors:
- Igor PakIPIgor Pak
- Greta PanovaGPGreta Panova
Preprint
Abstract
We study the complexity of computing Kronecker coefficients $g(\lambda,\mu,\nu)$. We give explicit bounds in terms of the number of parts $\ell$ in the partitions, their largest part size $N$ and the smallest second part $M$ of the three partitions. When $M = O(1)$, i.e. one of the partitions is hook-like, the bounds are linear in $\log N$, but depend exponentially on $\ell$. Moreover, similar bounds hold even when $M=e^{O(\ell)}$. By a separate argument, we show that the positivity of Kronecker coefficients can be decided in $O(\log N)$ time for a bounded number $\ell$ of parts and without restriction on $M$. Related problems of computing Kronecker coefficients when one partition is a hook, and computing characters of $S_n$ are also considered.
Keywords
All Related Versions
This publication has 37 references indexed in Scilit:
- Kronecker multiplicities in the (k, ℓ) hook are polynomially boundedIsrael Journal of Mathematics, 2014
- On rectangular Kronecker coefficientsJournal of Algebraic Combinatorics, 2010
- Reduced Kronecker Coefficients and Counter–Examples to Mulmuley’s Strong Saturation Conjecture SHcomputational complexity, 2009
- Nonzero Kronecker Coefficients and What They Tell us about SpectraCommunications in Mathematical Physics, 2007
- On the complexity of computing Kostka numbers and Littlewood-Richardson coefficientsJournal of Algebraic Combinatorics, 2006
- Algebraic Complexity Theory1997
- Stable properties of plethysm : on two conjectures of Foulkesmanuscripta mathematica, 1993
- On the Kronecker Product of Sn CharactersJournal of Algebra, 1993
- Hook young diagrams with applications to combinatorics and to representations of Lie superalgebrasAdvances in Mathematics, 1987
- Tensorprodukte von Charakteren der symmetrischen GruppeArchiv der Mathematik, 1977