A matrix is called rigid if one must change many of its entries before it becomes a low-rank matrix. Leslie Valiant introduced the notion in 1977 as a tool to prove lower bounds on the number of arithmetic operations needed to compute linear transformations like the discrete Fourier transform. Since then, many connections have been demonstrated between matrix rigidity and other topics in the theory of computation.

Unfortunately, proving that matrices of interest are rigid has shown to be a major challenge. In fact, it remains an open problem to prove that any explicit family of matrices is rigid. By contrast, it is known that a random matrix is rigid with high probability.

In this talk, I’ll give a brief overview of matrix rigidity and its uses in computer science. I’ll then discuss some recent results, including proofs that matrices like Hadamard and Fourier matrices, which were previously conjectured to be rigid, are in fact not rigid. The talk will not assume the audience has a background in computer science.