Output-sensitive classical algorithm conjecture for Kronecker coefficients

Let λ\lambda, mumu, and nunu be partitions of nn, and suppose that fλfmufnuf^{\lambda}\geq f^{mu}\geq f^{nu}. Kronecker algorithm conjecture. The Kronecker coefficient g(λ,mu,nu)g(\lambda,mu,nu) can be computed by a classical algorithm in time

O(fμfνfλpoly(n)).O\left(\frac{f^{\mu}f^{\nu}}{f^{\lambda}}\operatorname{poly}(n)\right).

The conjecture is posed as the opposite of the paper’s refuted expectation that no analogous classical algorithm exists for Kronecker coefficients. The paper proves efficient classical algorithms in substantial regimes, but the conjecture remains open in full generality.

Sources & referencesView supporting material

Primary source

Greta Panova, “Polynomial time classical versus quantum algorithms for representation theoretic multiplicities”, arXiv:2502.20253 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.