Matrix Rigidity

The notion of matrix rigidity was defined by Valiant in the 70s as a method for proving computational complexity lower bounds. A matrix is $(r,s)$-rigid if it has Hamming distance at least $s$ from any matrix of rank at most $r$. That is, one needs to change many entries to reduce the rank by much. While a random/generic matrix is highly rigid (say with $r=n/2$ and $s \sim cn^2$), there are no known examples (explicit constructions) matching, or getting anywhere near, these parameters. In this talk I will survey the state of the art on this problem and describe some recent results (joint with Allen Liu) showing that some natural candidates (Fourier, circulant, Toeplitz matrices) are in fact non rigid.