Matrix Rank – Extensions, Applications and Open Problems

on YouTube ↗01h 00m

" summary

Surveys concrete rank questions and what is known: matrix rigidity asks for explicit n×n A with r·s > n^{2+ε} (Hadamard gives r·s≈n^2), and no explicit construction beats the quadratic regime; Hadamard matrix and Johnson–Lindenstrauss give explicit approximate‑rank constructions but matching random bounds (≈log n/ε^2) remains open; tensor rank lower bounds for explicit d‑tensors only reach n^{d/2} by flattening while random tensors ≈n^{d−1}; algorithmic noncommutative rank testing reduces to invariant degree bounds (currently exponential upper bound), and a polynomial bound would yield PIT algorithms.

AI-written summary · about

" chapters (9)

1. 0:00Start
2. 1:57Basic Notion of Matrix Rank
3. 5:11Sylvester Matrix
4. 14:51Modular Space of Curves
5. 15:39Epsilon Rank of a Matrix
6. 20:29Sign Rank
7. 26:35The Projective Plane Matrix
8. 46:56Identity Tensor
9. 49:58Non-Commutative Rank

" related talks

• 01h 37mMatrix RigiditySatya Lokam · Algorithms and Complexity in Algebraic Geometry Boot Camp 2014
• 29mExtended Formulations and Information ComplexityAnkur Moitra · Information Theory in Complexity Theory and Combinatorics 2015
• 58mDichotomy Theorems for Counting Problems IXi Chen · Counting Complexity and Phase Transitions Boot Camp
• 50mRandom Combinatorial MatricesAmin Coja-Oghlan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 01h 00mAverage-case Complexity for Polynomials, and All ThatEmanuele Viola · Lower Bounds, Learning, and Average-Case Complexity
• 24mBlock Rigidity: Strong Multiplayer Parallel Repetition implies Super-Linear Lower Bounds for TuringRan Raz, Kunal Mittal · ITCS 2021
• 41mOn the Average-case Complexity of the Nearest Boolean Vector to a SubspaceAndrej Bogdanov · Lower Bounds, Learning, and Average-Case Complexity
• 30mA New Look at Gallager's BoundsNati Linial · Information Theory in Complexity Theory and Combinatorics 2015