Matrix rigidity

DOI10.1016/S0024-3795(99)00225-6zbMath0952.15002OpenAlexW4206039498MaRDI QIDQ1970501

Bruno Codenotti

Publication date: 3 January 2001

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0024-3795(99)00225-6

zbMATH Keywords

FFTlinear formslower boundsmatrix rankcomplexity theorymatrix rigiditynonlinear boundslinear circuits

Mathematics Subject Classification ID

Applications of graph theory to circuits and networks (94C15) Vector spaces, linear dependence, rank, lineability (15A03)

Related Items

Complexity of linear circuits and geometry, The minimum semidefinite rank of a triangle-free graph, On a theorem of Razborov, Using elimination theory to construct rigid matrices, Rigidity of a simple extended lower triangular matrix

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A remark on matrix rigidity
• A note on matrix rigidity
• A generalization of the Eckart-Young-Mirsky matrix approximation theorem
• On sparse graphs with dense long paths
• Graph-theoretic properties in computational complexity
• Improved lower bounds on the rigidity of Hadamard matrices
• Communication in bounded depth circuits
• Some combinatorial-algebraic problems from complexity theory
• Some structural properties of low-rank matrices related to computational complexity
• Applications of matrix methods to the theory of lower bounds in computational complexity
• The variation of the spectrum of a normal matrix
• The Smallest Perturbation of a Submatrix that Lowers the Rank of the Matrix
• The Smallest Perturbation of a Submatrix which Lowers the Rank and Constrained Total Least Squares Problems
• The Linear Complexity of Computation
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform