Matrix rigidity (Q1970501)

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.