Complexity of tropical Schur polynomials. (May 2016)

• Record Type: Journal Article
• Authors: Grigoriev, Dima; Koshevoy, Gleb
• Is Part Of: Journal of symbolic computation. Volume 74(2016)
• Page Start: 46
• Page End: 54
• Publication Date: 2016-05
• Subjects: Tropical Schur polynomials -- Complexity over the tropical semi-ring; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.05.005
• Languages: English
• ISSNs: 0747-7171

Abstract

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.