Higher Order MDS Codes
summary
Main claim: choosing Reed‑Solomon evaluation points at random over a large field yields codes that meet the list‑decoding Singleton bound, i.e., generic Reed‑Solomon codes are optimally list-decodable. Proof pivots on a new explicit formula for the dimension of intersections of column spans (max over partitions with a correction), and an equivalence showing higher‑order MDS = GZP = optimal average‑radius list decoding and ties to maximally recoverable tensor codes. Consequences: RS and many polynomial/AG constructions are generically optimal, but explicit small‑field constructions and efficient capacity‑achieving decoders remain open.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:19MDS codes and limitations
- 8:34Higher order MDS codes defined
- 13:05Connection to tensor codes
- 18:48List decoding and MDS
- 20:41Zero patterns in MDS
- 24:59Equivalence of properties
- 34:34Proof sketch for list-decodability
- 38:29Reed-Solomon and GM-MDS
- 40:20Existence over small fields
- 43:15Recent progress and open problems
related talks
41mHigh-Rate Fair-Density Parity-Check Codes
01h 09mWhen Cryptography Meets Modern Channel Coding
58mBosonic (And Other) Codes With Interesting Logical Gate Sets
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders
01h 06mAlgorithms for the k-List Problems
01h 00mError-Correcting Codes That Enable Efficient SNARKs
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes
12mAlgebraic Restriction Codes and their Applications