Kronecker Products, Low-Depth Circuits, and Matrix Rigidity

Josh Alman

For a matrix $M$ and a positive integer $r$, the rank $r$ rigidity of $M$ is the smallest number of entries of $M$ which one must change to make its rank at most $r$. There are man…