Teaching an old code a new trick

on YouTube ↗45m

" summary

Reed–Muller codes provably reach Shannon capacity on the binary erasure channel for every rate by combining three concrete facts: two-transitive symmetry of the code ensemble, the 1/log n sharp threshold for monotone symmetric subsets of the Hamming cube, and the EXIT/area identity that ties the integrated bit-erasure curve to code rate. Simulations show Reed–Muller outperforms polar codes at finite lengths; minimum distance scales ~sqrt(n), and the proof needs only symmetry not detailed weight spectra.

AI-written summary · about

" chapters (15)

1. 0:00Introduction
2. 0:50The standard setup
3. 2:34Probability of error
4. 4:02Codes on graphs
5. 7:22History
6. 8:58Polar codes
7. 16:36Achieving capacity
8. 17:58Symmetry
9. 19:12One transitive
10. 21:53Sharp thresholds
11. 26:27What this trick says
12. 29:39A trivial example
13. 32:53History of the trick
14. 34:06Putting it all together
15. 40:17Wrapping up

" related talks

• 33mGap to Capacity of Finite Length Polar CodesDavid Burshtein · Coding: From Practice to Theory
• 43mCoded matrix computation: numerical stability, partial stragglers and sparse input matricesAditya Ramamoorthy · Application-Driven Coding Theory 2024
• 26mAdaptive Coding over Countable AlphabetsStéphane Boucheron · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 37mSparse Superposition Codes for the AWGN Channel, Message Passing, Replica and Spatial CouplingFlorent Krzakala · Coding: From Practice to Theory
• 31mStatistical Estimation on GraphsAndrea Montanari · Coding: From Practice to Theory
• 44mErasures vs. Errors in Local Decoding and Property TestingSofya Raskhodnikova · Sublinear Algorithms and Nearest-Neighbor Search
• 01h 02mHow did we miss the random purification channel?Ewin Tang · Summer Cluster Final Workshop 2026
• 01h 11mPedagogical Talk: Failure of Low-Degree PolynomialsAlex Wein · Computational Phase Transitions (Simons Institute, 2020)