Sharp Thresholds for Random Subspaces, and Applications

on YouTube ↗01h 03m

" summary

Proves a sharp threshold for local properties of uniformly random subspaces over F_q: there's a rate r so dimension below r almost surely avoids any b-sized “bad” pattern, above r it almost surely contains one. Main characterization writes r as the maximum over linear projections of the simple expectation threshold; the only failure of first-moment is via such projections. Proof uses the second moment method; a key lemma shows a bad set appears in Gallager LDPC kernels with probability about 2^{-(1-ε)(n−k)b}, letting the result transfer to LDPC list-decodability up to capacity.

AI-written summary · about

" chapters (20)

1. 0:00Introduction
2. 0:49Outline
3. 3:09Random Subspaces
4. 7:27Questions
5. 10:55Review Question 1
6. 17:49Outline of Talk
7. 19:59Local Properties
8. 24:21First Moment Attempt
9. 27:31Is this the right threshold
10. 30:18Example
11. 34:12Theorem
12. 39:49Proof
13. 40:20Applications
14. 41:14LDPC Codes
15. 42:49Math Question
16. 43:11Math Theorem
17. 46:22Lemma
18. 48:42Intuition
19. 51:01Recap
20. 52:03Open Questions