Output-sensitive classical algorithm conjecture for Littlewood–Richardson coefficients

Let λ\lambda, mumu, and nunu be partitions such that λ=mu+nu|\lambda|=|mu|+|nu|. Assume cmu,nuλ>0c^{\lambda}_{mu,nu}>0. Output-sensitive Littlewood–Richardson conjecture. There exists a classical algorithm running in time

O(cμνλpoly(n))O\left(c^{\lambda}_{\mu\nu}\operatorname{poly}(n)\right)

that computes cμνλc^{\lambda}_{\mu\nu}. This is stated as a stronger conjecture because cμνλfλ/(fμfν)c^{\lambda}_{\mu\nu}\leq f^{\lambda}/(f^{\mu}f^{\nu}); it is known in restricted settings, including fixed-length cases, but remains open in general.

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.