Improved Decoding of Expander Codes

on YouTube ↗26m

" summary

Proves a new worst-case distance lower bound for any expander code: distance ≥ αn/(2ε) (and shows this is tight up to constants). Gives a linear-time decoder that corrects up to 3αn/(16ε) adversarial bit errors for ε<1/4. Main technical tool is a size-expansion trade-off lemma: any k·αn subset has neighbor size at least (1−kε)d·|S|, proved by a collision/probability argument. Algorithm combines modified belief propagation (threshold tuning from the guessed expansion) with Viderman-style recovery.

AI-written summary · about

" chapters (12)

1. 0:00Intro
2. 0:28Intro: Coding Theory Notations
3. 1:26Intro: Expanders
4. 4:19Intro: Expander codes
5. 6:10More about Expander Codes Theorem 1 (Sipser-Spielman 96)
6. 8:47Our Results (2)
7. 13:09Rest of the talk
8. 13:58Proof sketch for Theorem 2 (distance)
9. 17:35Proof Sketch of the size-expansion tradeoff Basic idea: A probabilistic argument about collisions Lemma 1
10. 21:19Ideas behind decoding radius Theorem 3 Given aand e=1/4-01 , 3 a linear-time algorithm that decodes N-ON errors for any expander code. Observation: Improve belief-propagation by guessing the expansion of the error set
11. 23:21Summary: Expander Codes
12. 24:30Discussion