Complexity of tropical Schur polynomials. (May 2016) - Grigoriev, Dima; Koshevoy, Gleb
Abstract: We study the complexity of computation of a tropical Schur polynomial Ts λ where λ is a partition, and of a tropical polynomial Tm λ obtained by the tropicalization of the monomial symmetric function m λ . Then Ts λ and 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 ⁡, + ) : a polynomial upper bound for Ts λ and an exponential lower bound for Tm λ . Also the complexity of tropical skew Schur polynomials is discussed.