On semiring complexity of Schur polynomials

DOI10.1007/S00037-018-0169-3MaRDI QIDQ1630378zbMATH OpenOpenAlexWikidataFDO

Authors Dorian Nogneng, Éric Schost, Sergey Fomin, Dima Grigoriev

Publication date 10 December 2018

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1608.05043, http://hdl.handle.net/21.11116/0000-0003-FD47-1

zbMATH Keywords

Schur functionsemiring complexityYoung tableaux

Mathematics Subject Classification ID

Symmetric functions and generalizations (05E05) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Analysis of algorithms and problem complexity (68Q25)

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_{l}ambda$ is $O(log(lambd{a}_1))$; here $lambd{a}_1$ is the largest part of the partition $lambda$.

Recommendations

• Complexity of tropical Schur polynomials
• Tropicalization, symmetric polynomials, and complexity
• scientific article; zbMATH DE number 4070302
• scientific article; zbMATH DE number 4045141
• scientific article; zbMATH DE number 1834647

Cites work

• A lower bound on the number of additions in monotone computations
• Accurate and efficient evaluation of Schur and Jack functions
• Accurate Computations with Totally Nonnegative Matrices
• Bruhat order of Coxeter groups and shellability
• Classical Bruhat orders and lexicographic shellability
• Complexity of tropical Schur polynomials
• Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten
• Generalized Quotients in Coxeter Groups
• scientific article; zbMATH DE number 3461412 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 739282 (Why is no real title available?)
• Negation can be exponentially powerful
• On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
• Poset topology: tools and applications
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Subtraction-free complexity, cluster transformations, and spanning trees

Cited in

(5)

• Tropicalization, symmetric polynomials, and complexity
• scientific article; zbMATH DE number 1836368 (Why is no real title available?)
• scientific article; zbMATH DE number 7561742 (Why is no real title available?)
• Schur polynomials do not have small formulas if the determinant does not
• Complexity of tropical Schur polynomials

Describes a project that uses

Uses Software

• TNTool

This page was built for publication: On semiring complexity of Schur polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1630378)