On the Complexity of Matrix Rank and Rigidity

DOI10.1007/978-3-540-74510-5_28MaRDI QIDQ3499780zbMATH OpenOpenAlexFDO

Authors Meena Mahajan, Jayalal Sarma M. N.

Publication date 3 June 2008

Published in Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-74510-5_28

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Determinants, permanents, traces, other special matrix functions (15A15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• On the complexity of matrix rank and rigidity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• scientific article; zbMATH DE number 37868
• Probabilistic rank and matrix rigidity

Cited in

(18)

• Maxwell-independence: a new rank estimate for the 3-dimensional generic rigidity matroid
• Probabilistic rank and matrix rigidity
• Max-min problems on the ranks and inertias of the matrix expressions \(A - BXC \pm (BXC)^{\ast}\) with applications
• The computational complexity of some problems of linear algebra (extended abstract)
• scientific article; zbMATH DE number 7204284 (Why is no real title available?)
• On the complexity of matrix rank and rigidity
• Matrix rank and communication complexity
• Rigidity of a simple extended lower triangular matrix
• The inverse of any two-by-two nonsingular partitioned matrix and three matrix inverse completion problems
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Relations between least-squares and least-rank solutions of the matrix equation \(AXB=C\)
• scientific article; zbMATH DE number 1555922 (Why is no real title available?)
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• ON THE RANK FUNCTION OF THE 3-DIMENSIONAL RIGIDITY MATROID
• Some optimization problems on ranks and inertias of matrix-valued functions subject to linear matrix equation restrictions
• Formulas for calculating the extremum ranks and inertias of a four-term quadratic matrix-valued function and their applications
• Solving optimization problems on ranks and inertias of some constrained nonlinear matrix functions via an algebraic linearization method

This page was built for publication: On the Complexity of Matrix Rank and Rigidity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3499780)