Before revision: The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r. Matrix rigidity was introduced by Valiant in 1977 as a tool to prove circuit lower bounds for linear functions and since then this notion has also found applications in other areas of complexity theory.
After revision: The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r. At MFCS'77, Valiant introduced matrix rigidity as a tool to prove circuit lower bounds for linear functions and since then this notion has also found applications in other areas of complexity theory.