Tropicalization, symmetric polynomials, and complexity

Alexander Woo, Alexander Yong

Research output: Contribution to journalArticlepeer-review

Abstract

D. Grigoriev-G. Koshevoy recently proved that tropical Schur polynomials have (at worst) polynomial tropical semiring complexity. They also conjectured tropical skew Schur polynomials have at least exponential complexity; we establish a polynomial complexity upper bound. Our proof uses results about (stable) Schubert polynomials, due to R. P. Stanley and S. Billey-W. Jockusch-R. P. Stanley, together with a sufficient condition for polynomial complexity that is connected to the saturated Newton polytope property.

Original languageEnglish (US)
Pages (from-to)242-249
Number of pages8
JournalJournal of Symbolic Computation
Volume99
DOIs
StatePublished - Jul 1 2020

Keywords

  • Schur polynomials
  • Tropical semiring complexity

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Tropicalization, symmetric polynomials, and complexity'. Together they form a unique fingerprint.

Cite this