Matrix rigidity
type: Item
instance of: scholarly article
title: Matrix rigidity
zbMATH Open document ID: 0952.15002
DOI: 10.1016/S0024-3795(99)00225-6
published in: Linear Algebra and its Applications
publication date: 2001-01-03T00:00:00Z
review text: Matrix rigidity has been introduced by \textit{L. G. Valiant} [Lect. Notes Comput. Sci. 53, 162-176 (1977; Zbl 0384.68046)] in connection with the complexity theory, namely that of proving nontrivial lower bounds on the length of computations. Valiant suggested that nonlinear lower bounds on the length of programs can be proved by constructing matrices satisfying given properties, based on the notion of matrix rigidity. The rigidity of a matrix \ \(M\) is the function \(R_{M}(r)\), which, for a given \(r\), gives the minimum number of entries of \(M\) which one has to change in order to reduce its rank to at most \(r\). The paper describes basic results and main open questions and provides some background on graphs which describes linear circuits.
reviewed by: M. Ladra
Mathematics Subject Classification ID: 15A03
Mathematics Subject Classification ID: 94C15
zbMATH DE Number: 1420040
zbMATH Keywords: matrix rigidity
zbMATH Keywords: lower bounds
zbMATH Keywords: linear forms
zbMATH Keywords: FFT
zbMATH Keywords: nonlinear bounds
zbMATH Keywords: matrix rank
zbMATH Keywords: complexity theory
zbMATH Keywords: linear circuits
author: Bruno Codenotti
MaRDI profile type: Publication
cites work: Q3852212
cites work: Some structural properties of low-rank matrices related to computational complexity
cites work: The Smallest Perturbation of a Submatrix which Lowers the Rank and Constrained Total Least Squares Problems
cites work: On sparse graphs with dense long paths
cites work: A note on matrix rigidity
cites work: Q5185900
cites work: A generalization of the Eckart-Young-Mirsky matrix approximation theorem
cites work: Q4109584
cites work: The variation of the spectrum of a normal matrix
cites work: Q3898625
cites work: Improved lower bounds on the rigidity of Hadamard matrices
cites work: Q3829670
cites work: Note on a Lower Bound on the Linear Complexity of the Fast Fourier Transform
cites work: The Linear Complexity of Computation
cites work: Q4234123
cites work: Communication in bounded depth circuits
cites work: Some combinatorial-algebraic problems from complexity theory
cites work: Boolean Circuits, Tensor Ranks, and Communication Complexity
cites work: Applications of matrix methods to the theory of lower bounds in computational complexity
cites work: Q4231904
cites work: A remark on matrix rigidity
cites work: Q4164821
cites work: Graph-theoretic properties in computational complexity
cites work: Q4036702
cites work: The Smallest Perturbation of a Submatrix that Lowers the Rank of the Matrix
full work available at URL: s0024-3795(99)00225-6
OpenAlex ID: W4206039498
description: scientific article; zbMATH DE number 1420040