The complexity of matrix rank and feasible systems of linear equations

DOI10.1007/s000370050023zbMath0949.68071OpenAlexW2171197316MaRDI QIDQ1961056

Eric W. Allender, Robert Beals, Ogihara, Mitsunori

Publication date: 5 December 2000

Published in: Computational Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s000370050023

zbMATH Keywords

natural complexity classes

Mathematics Subject Classification ID

Related Items (19)

Monomials, multilinearity and identity testing in simple read-restricted circuits ⋮ Evaluating Matrix Circuits ⋮ The parallel complexity of graph canonization under abelian group action ⋮ On the power of unambiguity in log-space ⋮ Bounded Treewidth and Space-Efficient Linear Algebra ⋮ Parameterised counting in logspace ⋮ The complexity of the characteristic and the minimal polynomial. ⋮ The orbit problem is in the GapL hierarchy ⋮ Towards a tight hardness-randomness connection between permanent and arithmetic circuit identity testing ⋮ The Orbit Problem Is in the GapL Hierarchy ⋮ Computing the sign or the value of the determinant of an integer matrix, a complexity survey. ⋮ ON THE MINIMAL POLYNOMIAL OF A MATRIX ⋮ Space Hardness of Solving Structured Linear Systems. ⋮ Evaluation of circuits over nilpotent and polycyclic groups ⋮ On the complexity of matrix rank and rigidity ⋮ On the complexity of noncommutative polynomial factorization ⋮ Counting classes and the fine structure between \(\mathrm{NC}^1\) and \(L\) ⋮ A note on closure properties of logspace MOD classes ⋮ Monomials in arithmetic circuits: complete problems in the counting hierarchy

This page was built for publication: The complexity of matrix rank and feasible systems of linear equations