Using Elimination Theory to Construct Rigid Matrices

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 (1977), rigidity and similar rank-robustness functions of matrices have found numerous applications in circuit complexity, communication complexity, and learning complexity. Almost all n × n matrices over an infinite field have a rigidity of (n − r)2. It is a long-standing open question to construct infinite families of explicit matrices even with superlinear rigidity when r = Ω(n).