Discrete Tori and Bounds for Linear Codes

on YouTube ↗42m

" summary

Recasts linear-code bounds by treating F2^n / C⊥ as a discrete torus and comparing metric balls there to Hamming balls; proves the torus second Laplacian eigenvalue equals 2D so any subset with Rayleigh ratio <2D must cover almost everything, recovering the linear‑program bound. Uses transport couplings and an Ollivier curvature lower bound (curvature ≥ 2/(n+1) for the cube) plus a diameter ≤ 2/κ argument to turn local weight‑3 parity constraints into a concrete size bound (radius ≲ (n+1)/(2(T+1))), improving bounds for LDPC codes.

AI-written summary · about

" chapters (19)

1. 0:00Binary codes
2. 1:17Simple bounds
3. 2:34The best known bound
4. 3:33Linear codes
5. 4:41The approach of Friedman and Tillich
6. 5:35Torus as a Cayley graph
7. 7:39Neighborhoods of zero
8. 11:16Comparison theorems
9. 15:02An aside on other proofs and extensions
10. 18:31What can we learn from this proof?
11. 19:13LDPC codes
12. 22:37Controlling growth of metric balls in tori
13. 27:51Some examples
14. 29:45Curvature in a cube
15. 31:41Curvature in a torus
16. 32:43Small highly constrained codes
17. 34:24Graphs with high curvature are small
18. 37:20Bounds on 2-LCCs using curvature
19. 38:302-LCCs with repeated coordinates