Low Rank Matrix Rigidity: Tight Lower Bounds and Hardness Amplification

Josh Alman, Jingxun Liang

For an $N\times N$ matrix $A$, its rank-$r$ rigidity, denoted ${\mathcal{R}}_A(r)$, is the minimum number of entries of $A$ that one must change to make its rank become at most $r$.…