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. Matrix rigidity was introduced by Valiant in 1977 as a tool to prove circuit lower bounds for linear functions and since then this notion received much attention and found applications in other areas of complexity theory.