Title: Tropicalization, symmetric polynomials, and complexity,
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.