Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time.

DOI10.4230/LIPIcs.ITCS.2017.55zbMath1402.68198OpenAlexW2794923896MaRDI QIDQ4638110

K. V. Subrahmanyam, Gábor Ivanyos, Youming Qiao

Publication date: 3 May 2018

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8166/pdf/LIPIcs-ITCS-2017-55.pdf/

zbMATH Keywords

invariant theorysemi-invariants of quiversnull conenon-commutative ranksymbolic determinant identity testing

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Vector and tensor algebra, theory of invariants (15A72) Actions of groups on commutative rings; invariant theory (13A50) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items (8)

Derandomization and absolute reconstruction for sums of powers of linear forms ⋮ Simultaneous robust subspace recovery and semi-stability of quiver representations ⋮ General linear group action on tensors: a candidate for post-quantum cryptography ⋮ Non-commutative Edmonds' problem and matrix semi-invariants ⋮ An exponential lower bound for the degrees of invariants of cubic forms and tensor actions ⋮ On rank-critical matrix spaces ⋮ Algorithms Based on *-Algebras, and Their Applications to Isomorphism of Polynomials with One Secret, Group Isomorphism, and Polynomial Identity Testing ⋮ The regularity lemma is false over small fields

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial degree bounds for matrix semi-invariants
• Vector spaces of matrices of low rank
• The eigenvalue problem \(\lambda Tx+Sx\)
• Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
• Classical complexity and quantum entanglement
• Computing Cartan subalgebras of Lie algebras
• Generalized Wong sequences and their applications to Edmonds' problems
• Non-commutative Edmonds' problem and matrix semi-invariants
• The Hilbert null-cone on tuples of matrices and bilinear forms
• Polynomial bounds for rings of invariants
• Arithmetic Circuits: A survey of recent results and open questions
• SMALL MAXIMAL SPACES OF NON-INVERTIBLE MATRICES
• THE CONSTRUCTIVE THEORY OF INVARIANTS
• Singular spaces of matrices and their application in combinatorics
• The word problem for free fields: a correction and an addendum
• ON THE CONSTRUCTION OF THE FREE FIELD
• On non-commutative rank and tensor rank
• Semi-invariants of quivers and saturation for Littlewood-Richardson coefficients
• The word problem for free fields
• Systems of distinct representatives and linear algebra
• Derandomizing polynomial identity tests means proving circuit lower bounds
• A deterministic strongly polynomial algorithm for matrix scaling and approximate permanents
• Semi-invariants of quivers as determinants
• Semi-invariants of quivers for arbitrary dimension vectors

This page was built for publication: Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time.