A Polynomial Degree Bound on Equations of Non-rigid Matrices and Small Linear Circuits

Mrinal Kumar, Ben Lee Volk

We show that there is a defining equation of degree at most $\mathsf{poly}(n)$ for the (Zariski closure of the) set of the non-rigid matrices: that is, we show that for every large…