On the complexity of matrix rank and rigidity

DOI10.1007/S00224-008-9136-8MaRDI QIDQ2268340zbMATH OpenOpenAlexFDO

Authors Meena Mahajan, Jayalal Sarma M. N.

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

complexity classesdeterminantmatrix rigiditymatrix rank

Mathematics Subject Classification ID

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

Recommendations

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

Cites work

• scientific article; zbMATH DE number 176871 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1261801 (Why is no real title available?)
• scientific article; zbMATH DE number 1263189 (Why is no real title available?)
• scientific article; zbMATH DE number 1332669 (Why is no real title available?)
• scientific article; zbMATH DE number 510841 (Why is no real title available?)
• scientific article; zbMATH DE number 733109 (Why is no real title available?)
• scientific article; zbMATH DE number 1161568 (Why is no real title available?)
• scientific article; zbMATH DE number 1405642 (Why is no real title available?)
• scientific article; zbMATH DE number 3204642 (Why is no real title available?)
• scientific article; zbMATH DE number 2196509 (Why is no real title available?)
• A compendium of problems complete for symmetric logarithmic space
• A fast parallel algorithm to compute the rank of a matrix over an arbitrary field
• A note on diagonally dominant matrices
• Arithmetic complexity, Kleene closure, and formal power series
• Checking robust nonsingularity is NP-hard
• Maximum rank matrix completion
• Natural proofs
• Nondeterministic NC^1 computation
• Problems complete for deterministic logarithmic space
• Relationships among $PL$, $\#L$, and the determinant
• Sampling-based dimension reduction for subspace approximation
• Structure and importance of logspace-MOD class
• Systems of linear interval equations
• The complexity of matrix rank and feasible systems of linear equations
• The computational complexity of some problems of linear algebra
• Undirected ST-connectivity in log-space

Cited in

(12)

• Maxwell-independence: a new rank estimate for the 3-dimensional generic rigidity matroid
• Probabilistic rank and matrix rigidity
• Rank reduction of oriented graphs by vertex and edge deletions
• The computational complexity of some problems of linear algebra (extended abstract)
• scientific article; zbMATH DE number 7204284 (Why is no real title available?)
• A polynomial degree bound on equations for non-rigid matrices and small linear circuits
• Matrix rank and communication complexity
• On the Complexity of Matrix Rank and Rigidity
• Spectral methods for matrix rigidity with applications to size-depth trade-offs and communication complexity
• Matrix Rigidity from the Viewpoint of Parameterized Complexity
• ON THE RANK FUNCTION OF THE 3-DIMENSIONAL RIGIDITY MATROID
• Pauli flow on open graphs with unknown measurement labels

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 Q2268340)