Reed-Muller and Other Subcodes of the Sierpinski Matrix

on YouTube ↗32m

" summary

Reed–Muller rows are reinterpreted via the Sierpinski tensor and a polarization of conditional ranks to build explicit parity matrices that meet a probabilistic Girth criterion; that gives N log N constructions (field-agnostic) achieving capacity on the BEC in some regimes. Weight‑enumerator bounds push degree R up to about m / log m; hashing plus affine‑invariance and generalized Hamming‑weight results yield guarantees that selected columns avoid dependencies and even allow roughly √N‑scale error/erasure correction in the high‑SNR regime.

AI-written summary · about

" chapters (8)

1. 0:00Intro
2. 0:36coding theory
3. 4:28The Serpiensky matrix
4. 8:18A proxy for the BEC error probability
5. 11:37A code achieves capacity on the BEC
6. 17:56The COR process
7. 22:56Results for problem 2
8. 29:05RM codes for BEC at high rate: high-girth property

" related talks

• 01h 14mPolar Codes IIIErdal Arikan · Information Theory Boot Camp 2015
• 01h 19mTutorial 2: Algorithmic Invariant TheoryBernd Sturmfels · Geometric Complexity Theory 2014
• 57mComputing Multiplicities of Lie Group RepresentationsMatthias Christandl · Geometric Complexity Theory 2014
• 39mStructure of the Fourier Spectrum of Boolean Functions and ComplexityBen Lee Volk · Neo-Classical Methods in Discrete Analysis 2013
• 29mApproximating the Permanent of Positive Semidefinite MatricesNima Anari · Discrete Optimization via Continuous Relaxation
• 10mOn the Generality of Matrix MultiplicationJonathan Balkind, Zachary D. Sisco, Andrew Alex · PLARCH 2023
• 23mKarchmer-Wigderson Games for Hazard-free ComputationChristian Ikenmeyer, Balagopal Komarath, Nitin Saurabh · ITCS 2023
• 01h 01mTrue Complexity of Multilinear SystemsFreddie Manners · Structure vs. Randomness 2017