Opening Expander Graphs Application 1: Good Codes
Expander Graphs Application 1: Good Codes
- Length
- 26 min
- Level
- Graduate
- Recorded
- Carnegie Mellon University2020
Chapter 1 of 4: Bipartite expander graphs and error-correcting codes
Expander codes, following papers by Tanner and by Sipser and Spielman, give good binary error-correcting codes with polynomial-time decoding from explicit bipartite expanders. O'Donnell starts from a left-regular bipartite graph with strong expansion and proves that every sufficiently small left set has a unique neighbor on the right. Taking the adjacency matrix as a parity check matrix defines a linear code over with rate at least . The unique neighbor claim then bounds the minimum distance below by the largest set the expansion covers. The final part gives a decoder that flips any bit reducing the number of failed parity checks, and shows it runs in polynomial time. Part of lecture 16b of CMU's graduate CS Theory Toolkit, it assumes expanders and linear codes.
Your comment is kept while you sign up.Sign in
Proves small sets in a bipartite expander have unique neighbors, then uses this to bound an expander code's distance.
Expander codes, following papers by Tanner and by Sipser and Spielman, give good binary error-correcting codes with polynomial-time decoding from explicit bipartite expanders. O'Donnell starts from a left-regular bipartite graph with strong expansion and proves that every sufficiently small left set has a unique neighbor on the right. Taking the adjacency matrix as a parity check matrix defines a linear code over with rate at least . The unique neighbor claim then bounds the minimum distance below by the largest set the expansion covers. The final part gives a decoder that flips any bit reducing the number of failed parity checks, and shows it runs in polynomial time. Part of lecture 16b of CMU's graduate CS Theory Toolkit, it assumes expanders and linear codes.
Papers by Tanner, and Sipser and Spielman
This lecture
Lecture 50 of 89 of A Theorist's Toolkit.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. What comes after is on the rightat the bottom. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.