List Recovery and Local Decoding of Expander Codes
summary
Shows that taking a D‑regular Ramanujan expander and an inner code with modest local structure yields an outer Tanner/expander code with concrete guarantees: codes of rate tending to one that are locally correctable with q = n^ε queries (for some ε>0 and error fraction δ = 1/poly(q)), and codes admitting linear time list recovery from erasures with constant list size. Uses spectral expansion (second eigenvalue bounds), local list recovery of the inner code, and propagation across the expander to get the claimed query/list-size bounds.
AI-written summary · about
chapters (12)
- 0:00Intro
- 0:30One slide version
- 2:23Overview of results
- 9:11Tanner Codes [Tanner'81]
- 14:00High rate locally-correctable codes
- 15:19Instantiate with codes from affine geometries
- 17:26List Recovery
- 20:07Linear-time list-recoverable codes
- 20:27Instantiate with random linear codes
- 21:39Algorithm for list-recovery
- 24:20Local Correction
- 26:00Moral of the story
related talks
37mMaximally Recoverable Codes
51mConvertible codes: Adaptive coding for large-scale data storage
20mCounting and Sampling Perfect Matchings in Regular Expanding Non-Bipartite Graphs
28mTowards Practical Polar Codes With Low Scaling Exponent
11mExploiting Combined Locality for Wide-Stripe Erasure Coding in Distributed Storage
44mTutorial on List Decodable Coding Schemes and Interactive Communication in Networks (Part 2 of 2)
31mAlgebraic Coding Problems From Quantum Fault-Tolerance
18mList Agreement Expansion from Coboundary Expansion