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

• The stability of the Kronecker products of Schur functions
• Reduced Kronecker coefficients and counter-examples to Mulmuley's strong saturation conjecture SH
• 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 (9)

• Unifying and generalizing known lower bounds via geometric complexity theory
• Invariant Operators, Orthogonal Bases and Correlators in General Tensor Models
• Computing Multiplicities of Lie Group Representations
• Bounds on the Kronecker coefficients
• Complexity of short Presburger arithmetic
• Positivity of the symmetric group characters is as hard as the polynomial time hierarchy
• Bounds on Kronecker and $q$-binomial coefficients
• Counting Integer Points in Multi-Index Transportation Polytopes
• The Saxl Conjecture and the Dominance Order