The University of Michigan Combinatorics Seminar


Abstract 

The rigidity of a matrix is the minimum number of its entries
to be changed in order to reduce its rank, say, by a constant fraction.
While it is known for more than 25 years that "almost all"
n by n
matrices have rigidity close to n^{2},
no superlinear lower bounds are
known on the rigidity of explicit matrices. The quest for explicit
matrices with high rigidity is motivated by a variety of applications in
computational complexity theory. We will survey a few known results and
describe several open questions about rigidity and similar
rankrobustness measures.
