Matrix Rigidity
summary
Defines rigidity as the minimum entries to change to drop rank to R and ties large rigidity for R = εN to impossibility of depth‑log N, linear‑size linear circuits via Valiant's criterion. Generic matrices have rigidity ≈(N−R)^2 but known explicit lower bounds reach only S = Ω(N^2 / R · log(N/R)) using combinatorial Zarankiewicz bounds, error‑correcting code constructions and superconcentrator counterexamples, while algebraic‑geometry and number‑field constructions (e.g. entries √p or Cauchy/Vandermonde variants) push toward near‑quadratic rigidity but rely on nonrational entries; proving high rigidity for Fourier/Vandermonde over cyclotomic fields or in polynomial‑degree number fields remains open.
AI-written summary · about
chapters (22)
- 0:00Introduction
- 0:22Matrix rigidity definition
- 2:14Upper and lower bounds
- 4:20Explicit matrix challenge
- 5:40Arithmetic complexity
- 10:51Valiant's theorem reduction
- 13:58Totally regular matrices
- 18:48Combinatorial rigidity bounds
- 25:57Rank condition translation
- 31:04Conclusion on regularity
- 34:52Error-correcting codes
- 37:12Code-based matrix bounds
- 40:36Limitation of total regularity
- 45:35Shoup-Smolensky dimension
- 50:58Low rank matrix proof
- 58:50Algebraic geometry perspective
- 1:02:56Rigidity varieties
- 1:09:45Elimination ideals
- 1:14:34Effective measurements
- 1:19:37Recent results and open questions
- 1:23:44Roots of unity matrices
- 1:26:18Final discussion and Q&A
related talks
01h 00mMatrix Rank – Extensions, Applications and Open Problems
24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for Turing
29mExtended Formulations and Information Complexity
01h 01mCoding for Modern Distributed Storage Systems I
01h 00mAverage-case Complexity for Polynomials, and All That
58mDichotomy Theorems for Counting Problems I
30mA New Look at Gallager's Bounds
48mUnstructured Hardness to Average-Case Randomness