Vanishing of Littlewood–Richardson polynomials is in P

Anshul Adve, Colleen Robichaux, Alexander Yong

Research output: Contribution to journalArticlepeer-review


J. De Loera & T. McAllister and K. D. Mulmuley & H. Narayanan & M. Sohoni independently proved that determining the vanishing of Littlewood–Richardson coefficients has strongly polynomial time computational complexity. Viewing these as Schubert calculus numbers, we prove the generalization to the Littlewood–Richardson polynomials that control equivariant cohomology of Grassmannians. We construct a polytope using the edge-labeled tableau rule of H. Thomas, A. Yong. Our proof then combines a saturation theorem of D. Anderson, E. Richmond, A. Yong, a reading order independence property, and É. Tardos’ algorithm for combinatorial linear programming.

Original languageEnglish (US)
Pages (from-to)241-257
Number of pages17
JournalComputational Complexity
Issue number2
StatePublished - Jun 1 2019


  • 03D15
  • 05E015
  • 14M15
  • Schubert calculus
  • computational complexity
  • equivariant cohomology
  • factorial Schur functions

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Mathematics
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Vanishing of Littlewood–Richardson polynomials is in P'. Together they form a unique fingerprint.

Cite this