On the complexity of matrix rank and rigidity

DOI10.1007/S00224-008-9136-8zbMATH Open1183.68295OpenAlexW2077143506MaRDI QIDQ2268340FDOQ2268340

Jayalal Sarma M. N., Meena Mahajan

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)

Cites Work

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

Cited In (8)

• 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
• Title not available (Why is that?)
• Matrix rank and communication complexity
• 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

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)