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...
This data center is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.
We found no citations for this text. For information on how to provide citation information, please see our documentation.