The computational complexity of some problems of linear algebra (extended abstract)

DOI10.1007/BFB0023480MaRDI QIDQ5048945zbMATH OpenOpenAlexFDO

Authors Jonathan F. Buss, Gudmund S. Frandsen, Jeffrey Shallit

Publication date 9 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

matrix rank

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Vector spaces, linear dependence, rank, lineability (15A03)

Recommendations

• The computational complexity of some problems of linear algebra
• On the complexity of matrix rank and rigidity
• scientific article; zbMATH DE number 1256731
• On the Complexity of Matrix Rank and Rigidity
• The complexity of matrix rank and feasible systems of linear equations

Cites work

• scientific article; zbMATH DE number 3876606 (Why is no real title available?)
• scientific article; zbMATH DE number 42574 (Why is no real title available?)
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 3597878 (Why is no real title available?)
• scientific article; zbMATH DE number 1261801 (Why is no real title available?)
• scientific article; zbMATH DE number 1306875 (Why is no real title available?)
• A note on matrix rigidity
• Fast Probabilistic Algorithms for Verification of Polynomial Identities
• On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals

Cited in

(8)

• Computational Complexity and Numerical Stability of Linear Problems
• scientific article; zbMATH DE number 2072707 (Why is no real title available?)
• The complexity of linear problems in fields
• Interval Linear Algebra and Computational Complexity
• Combinatorial optimization methods to determine the rank of a matrix over a commutative ring, with engineering applications
• The bit complexity of matrix multiplication and of related computations in linear algebra. The segmented \(\lambda\) algorithms
• Communication complexity of matrix computation over finite fields
• The complexity of matrix rank and feasible systems of linear equations

This page was built for publication: The computational complexity of some problems of linear algebra (extended abstract)

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