The University of Michigan Combinatorics Seminar
Winter 2002
March 22, 4:10-5:00, 3866 East Hall

Matrix rigidity -- a survey

Satyanarayana Lokam

University of Michigan


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 n2, 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 rank-robustness measures.