On semiring complexity of Schur polynomials

DOI10.1007/S00037-018-0169-3zbMATH Open1408.68072arXiv1608.05043OpenAlexW2515773438WikidataQ105613624 ScholiaQ105613624MaRDI QIDQ1630378FDOQ1630378

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

Publication date: 10 December 2018

Published in: Computational Complexity (Search for Journal in Brave)

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$.

Full work available at URL: https://arxiv.org/abs/1608.05043

zbMATH Keywords

Young tableauxSchur functionsemiring complexity

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Schur polynomials do not have small formulas if the determinant does not
• Title not available (Why is that?)

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)