Using Elimination Theory to construct Rigid Matrices

Abhinav Kumar, Satyanarayana V. Lokam, Vijay M. Patankar & Jayalal Sarma M. N.
The rigidity of a matrix $A$ for target rank $r$ is the minimum number of entries of $A$ that must be changed to ensure that the rank of the altered matrix is at most $r$. Since its introduction by Valiant \cite{Val77}, rigidity and similar rank-robustness functions of matrices have found numerous applications in circuit complexity, communication complexity, and learning complexity. Almost all $\nbyn$ matrices over an infinite field have a rigidity of $(n-r)^2$. It is...