Constructive non-commutative rank computation is in deterministic polynomial time
From MaRDI portal
Publication:1630376
Abstract: We extend our techniques developed in our earlier paper appeared in Computational Complexity, 2017 (preprint: arXiv:1508.00690) to obtain a deterministic polynomial time algorithm for computing the non-commutative rank together with certificates of linear spaces of matrices over sufficiently large base fields. The key new idea is a reduction procedure that keeps the blow-up parameter small, and there are two methods to implement this idea: the first one is a greedy argument that removes certain rows and columns, and the second one is an efficient algorithmic version of a result of Derksen and Makam. Both methods rely crucially on the regularity lemma in our aforementioned paper, and in this manuscript we also improve that lemma by removing a coprime condition there.
Recommendations
- Constructive non-commutative rank computation is in deterministic polynomial time
- Non-commutative Edmonds' problem and matrix semi-invariants
- Almost settling the hardness of noncommutative determinant
- scientific article; zbMATH DE number 7204284
- A deterministic PTAS for the commutative rank of matrix spaces
Cites work
- A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
- A Prime Matrix Ideal Yields a Skew Field
- Classical complexity and quantum entanglement
- Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
- Computing Cartan subalgebras of Lie algebras
- Derandomizing polynomial identity tests means proving circuit lower bounds
- Generalized Wong sequences and their applications to Edmonds' problems
- scientific article; zbMATH DE number 3741566 (Why is no real title available?)
- scientific article; zbMATH DE number 798609 (Why is no real title available?)
- scientific article; zbMATH DE number 3336601 (Why is no real title available?)
- Non-commutative arithmetic circuits with division
- Non-commutative Edmonds' problem and matrix semi-invariants
- On non-commutative rank and tensor rank
- ON THE CONSTRUCTION OF THE FREE FIELD
- Polynomial bounds for rings of invariants
- Polynomial degree bounds for matrix semi-invariants
- Rational identities and applications to algebra and geometry
- Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients
- Semi-invariants of quivers as determinants
- Semi-invariants of quivers for arbitrary dimension vectors
- Systems of distinct representatives and linear algebra
- The computational complexity of some problems of linear algebra
- The eigenvalue problem \(\lambda Tx+Sx\)
- The Hilbert null-cone on tuples of matrices and bilinear forms
- Tighter connections between derandomization and circuit lower bounds
- Vector spaces of matrices of low rank
Cited in
(47)- Wildness for tensors
- Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
- A compact representation for modular semilattices and its applications
- A standard form in (some) free fields: how to construct minimal linear representations
- Singular tuples of matrices is not a null cone (and the symmetries of algebraic varieties)
- 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 2 submatrices
- Computing valuations of the Dieudonné determinants
- Polystability in positive characteristic and degree lower bounds for invariant rings
- Ideals of spaces of degenerate matrices
- Information geometry of operator scaling
- A cost-scaling algorithm for computing the degree of determinants
- Algorithms for orbit closure separation for invariants and semi-invariants of matrices
- On a weighted linear matroid intersection algorithm by deg-det computation
- Operator scaling: theory and applications
- Non-commutative Edmonds' problem and matrix semi-invariants
- Ranks of linear matrix pencils separate simultaneous similarity orbits
- Weighted slice rank and a minimax correspondence to Strassen's spectra
- A deterministic PTAS for the commutative rank of matrix spaces
- Constructive non-commutative rank computation is in deterministic polynomial time
- Computing the nc-Rank via Discrete Convex Optimization on CAT(0) Spaces
- From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: another bridge between graphs and alternating matrix spaces
- Invariant Theory and Scaling Algorithms for Maximum Likelihood Estimation
- Maximum likelihood estimation for matrix normal models via quiver representations
- A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices
- A Special Case of Rational Identity Testing and the Brešar-Klep Theorem.
- scientific article; zbMATH DE number 7561740 (Why is no real title available?)
- Maximum likelihood estimation for tensor normal models via castling transforms
- Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings
- A deterministic PTAS for the algebraic rank of bounded degree polynomials
- Efficient Black-Box Identity Testing for Free Group Algebras
- Connections between graphs and matrix spaces
- A combinatorial algorithm for computing the entire sequence of the maximum degree of minors of a generic partitioned polynomial matrix with 2 2 submatrices
- A deterministic Algorithm for Harder-Narasimhan filtrations for representations of acyclic quivers
- The separating variety for matrix semi-invariants
- Harder-Narasimhan filtrations and zigzag persistence
- A bridge between invariant theory and maximum likelihood estimation
- Algebraic algorithms for fractional linear matroid parity via noncommutative rank
- On solving (non)commutative weighted Edmonds' problem
- Computing the noncommutative inner rank by means of operator-valued free probability theory
- Complexity of robust orbit problems for torus actions and the abc-conjecture
- A multivariate to bivariate reduction for noncommutative rank and related results
- A scaling characterization of NC-rank via unbounded gradient flow
- Algebraic combinatorial optimization on the degree of determinants of noncommutative symbolic matrices
- On efficient noncommutative polynomial factorization via Higman linearization
- Fractional linear matroid matching is in quasi-NC
- Algorithmic aspects of semistability of quiver representations
This page was built for publication: Constructive non-commutative rank computation is in deterministic polynomial time
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1630376)
