On the complexity of matrix rank and rigidity

DOI10.1007/s00224-008-9136-8zbMath1183.68295OpenAlexW2077143506MaRDI QIDQ2268340

Meena Mahajan, M. N. Jayalal Sarma

Publication date: 5 March 2010

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-008-9136-8

zbMATH Keywords

determinantmatrix rankcomplexity classesmatrix rigidity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

Rank reduction of oriented graphs by vertex and edge deletions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Systems of linear interval equations
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• Nondeterministic \(NC^1\) computation
• Maximum rank matrix completion
• The computational complexity of some problems of linear algebra
• Arithmetic complexity, Kleene closure, and formal power series
• A note on diagonally dominant matrices
• Checking robust nonsingularity is NP-hard
• The complexity of matrix rank and feasible systems of linear equations
• Sampling-based dimension reduction for subspace approximation
• Undirected ST-connectivity in log-space
• Problems complete for deterministic logarithmic space
• Structure and importance of logspace-MOD class
• Relationships among $PL$, $\#L$, and the determinant
• Natural proofs
• A compendium of problems complete for symmetric logarithmic space