Classical output-sensitive algorithm conjecture for Littlewood–Richardson coefficients

Let \bla\bla, \bmu\bmu, and \bnu\bnu be partitions such that \bla=\bmu+\bnu|\bla|=|\bmu|+|\bnu|. Littlewood–Richardson algorithm conjecture. There exists a classical algorithm running in time

O(f\blaf\bmuf\bnupoly(n))O\left(\frac{f^\bla}{f^\bmu f^\bnu}\operatorname{poly}(n)\right)

that computes the Littlewood–Richardson coefficient c\bmu\bnu\blac^\bla_{\bmu\bnu}. The conjecture is a proposed classical counterpart to the known quantum runtime, with polynomial-time algorithms already available in some restricted cases such as fixed ell(\bla)ell(\bla); the general case remains open.

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.