Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
From MaRDI portal
Publication:4959125
DOI10.1137/20M138836XMaRDI QIDQ4959125
Publication date: 10 September 2021
Published in: SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2012.13651
CAT(0) spacesubmodular functionmodular latticeproximal point algorithmEdmonds' problemnoncommutative rank
Analysis of algorithms and problem complexity (68Q25) Convex programming (90C25) Complemented modular lattices, continuous geometries (06C20)
Related Items
A cost-scaling algorithm for computing the degree of determinants ⋮ Minimizing submodular functions on diamonds via generalized fractional matroid matchings ⋮ Old and new challenges in Hadamard spaces ⋮ Connections between graphs and matrix spaces ⋮ Submodule codes as spherical codes in buildings ⋮ A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with \(2 \times 2\) submatrices ⋮ Interactions of computational complexity theory and mathematics ⋮ A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with \(2\times 2\) submatrices ⋮ A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices ⋮ Computing valuations of the Dieudonné determinants
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The 6-strand braid group is \(\mathrm{CAT}(0)\).
- Polynomial degree bounds for matrix semi-invariants
- Braids, posets and orthoschemes
- On the complexity of submodular function minimisation on diamonds
- Discrete-time gradient flows and law of large numbers in Alexandrov spaces
- Geometry of the space of phylogenetic trees
- Constructive non-commutative rank computation is in deterministic polynomial time
- Computing DM-decomposition of a partitioned matrix with rank-1 blocks
- Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
- Classical complexity and quantum entanglement
- Noncommutative rational functions, their difference-differential calculus and realizations
- The proximal point algorithm in metric spaces
- Operator scaling: theory and applications
- Non-commutative Edmonds' problem and matrix semi-invariants
- On graphs and rigidity of plane skeletal structures
- Submodular functions and optimization.
- A polynomial time algorithm to compute geodesics in CAT(0) cubical complexes
- Convex analysis and optimization in Hadamard spaces
- Computing Medians and Means in Hadamard Spaces
- Lattice Theory: Foundation
- Computing Geodesic Distances in Tree Space
- Weakly Modular Graphs and Nonpositive Curvature
- Buildings
- Singular spaces of matrices and their application in combinatorics
- Block-Triangularizations of Partitioned Matrices Under Similarity/Equivalence Transformations
- Discrete Convex Analysis
- L-CONVEXITY ON GRAPH STRUCTURES
- A Minimax Theorem and a Dulmage–Mendelsohn Type Decomposition for a Class of Generic Partitioned Matrices
- Operator scaling via geodesically convex optimization, invariant theory and polynomial identity testing
- Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
- A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
- Systems of distinct representatives and linear algebra
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Matrices and matroids for systems analysis
