On the complexity of computing Kronecker coefficients

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.

v3: incorporated referee's comments; accepted to Computational Complexity

References in corpus (5)

• Geometric Complexity Theory VI: the flip via saturated and positive integer programming in representation theory and algebraic geometry
• Kronecker coefficients for one hook shape
• Kronecker products, characters, partitions, and the tensor square conjectures
• The partition algebra and the Kronecker coefficients
• Kronecker multiplicities in the $(k,\ell )$ hook are polynomially bounded

Cited by in corpus (3)

• Computing Multiplicities of Lie Group Representations
• Bounds on the Kronecker coefficients
• The Saxl Conjecture and the Dominance Order