On semiring complexity of Schur polynomials

Abstract

Semiring complexity is the version of arithmetic circuit complexity that allows only two operations: addition and multiplication. We show that when the number of variables is fixed, the semiring complexity of a Schur polynomial $s_{\lambda }$ is $O(log({\lambda }_1))$; here ${\lambda }_1$ is the largest part of the partition $\lambda$.

22 pages, final version, to appear in Computational Complexity. Section 4 rewritten per referee's suggestion, to make the argument more explicit

Cited by in corpus (1)

• Tropicalization, symmetric polynomials, and complexity