Complexity of tropical Schur polynomials

We study the complexity of computation of a tropical Schur polynomial TsλTsλ where λ   is a partition, and of a tropical polynomial TmλTmλ obtained by the tropicalization of the monomial symmetric function mλmλ. Then TsλTsλ and TmλTmλ coincide as tropical functions (so, as convex piece-wise linear functions), while differ as tropical polynomials. We prove the following bounds on the complexity of computing over the tropical semi-ring (R,max⁡,+)(R,max⁡,+):
• a polynomial upper bound for TsλTsλ and
• an exponential lower bound for TmλTmλ. Also the complexity of tropical skew Schur polynomials is discussed.