Subtraction-free complexity, cluster transformations, and spanning trees
From MaRDI portal
Publication:5963078
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
spanning treeSchur functionarithmetic circuitcluster transformationstar-mesh transformationsubtraction-free complexity
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
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