Vanishing of Littlewood–Richardson polynomials is in P

Anshul Adve, Colleen Robichaux, Alexander Yong

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume28
Issue number2
DOIs
StatePublished - Jun 1 2019

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Fingerprint

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

Cite this