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

on YouTube ↗27m

" summary

Paper proves an explicit existential bound: for non-rigid n-by-n matrices with parameters εn and εn^2 there exists an equation of degree O(n^3) vanishing on their Zariski closure, found by building a low-degree polynomial map Q that captures all such matrices. Construction uses UV factorization for low rank and Lagrange interpolation for sparsity to produce Q with 4ε n^2 variables and degree ≤ n^2. Result is non-constructive; consequences tie to PIT and a PSPACE versus NP-oracle win‑win for rigidity.

AI-written summary · about

" chapters (4)

1. 0:00Start
2. 5:32ALGEBRAIC PROOFS FOR LOWER BOUNDS A non-zero polynomial Pel(U) is called an equation for U.
3. 13:06UNIVERSAL MAP FOR NON-RIGID MATRICES Lemma: There's a polynomial map Q:+C*** of degreer whose image contains all matrices which are not (en en)-rigid.
4. 21:50PROOF SKETCH The equations we find are solutions to a linear systern of exponential size and we can output a solution in PSPACE using standard Smal-space algorithm for linear algebra.