Subtraction-free complexity, cluster transformations, and spanning trees

DOI10.1007/s10208-014-9231-yzbMath1352.68104arXiv1307.8425OpenAlexW1976802094WikidataQ105613658 ScholiaQ105613658MaRDI QIDQ5963078

Gleb A. Koshevoy, Dima Yu. Grigoriev, Fomin, Sergey

Publication date: 4 March 2016

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

spanning treeSchur functionarithmetic circuitcluster transformationstar-mesh transformationsubtraction-free complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symmetric functions and generalizations (05E05) Cluster algebras (13F60)

Related Items

On semiring complexity of Schur polynomials, Integer complexity and well-ordering, Shadows of Newton polytopes, ReLU neural networks of polynomial size for exact maximum flow computation, Schur polynomials do not have small formulas if the determinant does not, Lower bounds for tropical circuits and dynamic programs, Unnamed Item, Approximation Limitations of Pure Dynamic Programming, Sorting can exponentially speed up pure dynamic programming

Uses Software

• TNTool

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Comultiplication rules for the double Schur functions and Cauchy identities
• Lower bounds in algebraic computational complexity
• Negation can be exponentially powerful
• A lower bound on the number of additions in monotone computations
• A new tableau representation for supersymmetric Schur functions
• Schur functions: Theme and variations
• Matroid inequalities from electrical network theory
• Parametrizations of canonical bases and totally positive matrices
• Computing the singular value decomposition with high relative accuracy
• On computing Schur functions and series thereof
• On the complexity of computing Kostka numbers and Littlewood-Richardson coefficients
• Idempotent and tropical mathematics; complexity of algorithms and interval analysis
• Cluster algebras I: Foundations
• Separated set-systems and their geometric models
• Arithmetic Circuits: A survey of recent results and open questions
• Accurate Computations with Totally Nonnegative Matrices
• Some Exact Complexity Results for Straight-Line Computations over Semirings
• Accurate and efficient evaluation of Schur and Jack functions
• A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.
• Complexity of Null- and Positivstellensatz proofs