Generalized Wong sequences and their applications to Edmonds' problems

DOI10.1016/j.jcss.2015.04.006zbMath1320.68222arXiv1307.6429OpenAlexW2200115418MaRDI QIDQ2353409

Miklos Santha, Marek Karpinski, Gábor Ivanyos, Youming Qiao

Publication date: 13 July 2015

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

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

zbMATH Keywords

derandomizationWong sequencesmaximum rank matrix completionEdmonds' problemsymbolic determinantal identity testing

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Nonnumerical algorithms (68W05) Determinants, permanents, traces, other special matrix functions (15A15) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Matrix pencils (15A22)

Related Items

A Combinatorial Algorithm for Computing the Rank of a Generic Partitioned Matrix with 2 $$\times $$ 2 Submatrices ⋮ Constructive non-commutative rank computation is in deterministic polynomial time ⋮ Constructive Non-Commutative Rank Computation Is in Deterministic Polynomial Time. ⋮ Simultaneous robust subspace recovery and semi-stability of quiver representations ⋮ Non-commutative Edmonds' problem and matrix semi-invariants ⋮ On rank-critical matrix spaces ⋮ Connections between graphs and matrix spaces ⋮ A deterministic Algorithm for Harder-Narasimhan filtrations for representations of acyclic quivers ⋮ Unnamed Item ⋮ Operator scaling: theory and applications ⋮ Computing the Degree of Determinants via Discrete Convex Optimization on Euclidean Buildings ⋮ From Independent Sets and Vertex Colorings to Isotropic Spaces and Isotropic Decompositions: Another Bridge between Graphs and Alternating Matrix Spaces ⋮ Edmonds' problem and the membership problem for orbit semigroups of quiver representations ⋮ Sinkhorn-Knopp theorem for PPT states ⋮ A combinatorial algorithm for computing the rank of a generic partitioned matrix with \(2 \times 2\) submatrices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On computing the determinant in small parallel time using a small number of processors
• Vector spaces of matrices of low rank
• The eigenvalue problem \(\lambda Tx+Sx\)
• Maximum rank matrix completion
• The computational complexity of some problems of linear algebra
• The linear delta-matroid parity problem
• Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank
• Classical complexity and quantum entanglement
• Computing Cartan subalgebras of Lie algebras
• Matroid matching via mixed skew-symmetric matrices
• The Quasi-Kronecker Form For Matrix Pencils
• Generalized Wong sequences and their applications to Edmonds' problems
• The complexity of matrix completion
• Greatest common divisors of polynomials given by straight-line programs
• Singular spaces of matrices and their application in combinatorics
• SPACES OF MATRICES OF BOUNDED RANK
• Solution Concepts for Linear DAEs: A Survey
• Addition to “The Quasi-Kronecker Form for Matrix Pencils
• Deterministic Polynomial Time Algorithms for Matrix Completion Problems
• Systems of distinct representatives and linear algebra
• On Matroid Theorems of Edmonds and Rado
• A THEOREM ON INDEPENDENCE RELATIONS
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Matrices and matroids for systems analysis

This page was built for publication: Generalized Wong sequences and their applications to Edmonds' problems