List-decoding random codes ensembles
summary
Random linear codes over F2 are shown to match random (nonlinear) codes: rate 1−H(p)−ε is list-decodable to radius p with list size roughly Θ(H(p)/ε) and that bound is tight up to lower-order terms, improving prior 2^{1/ε} bounds via a potential-function growth argument and a concentration proof. Over large alphabets, randomly punctured Reed–Solomon codes reach capacity; proofs reduce to showing reduced intersection matrices + Schwartz–Zippel are full rank and then cut alphabet to linear in n.
AI-written summary · about
chapters (11)
- 0:00Introduction
- 1:05What is list-decoding
- 5:30Capacity theorem overview
- 8:17Random linear binary codes
- 16:30Nonbinary alphabets open questions
- 18:39Reed-Solomon motivation
- 20:55Reed-Solomon bounds history
- 29:40Alphabet reduction in RS codes
- 31:06Proof key ideas
- 41:16GM-MDS theorem
- 43:04Summary
related talks
41mHigh-Rate Fair-Density Parity-Check Codes
01h 09mWhen Cryptography Meets Modern Channel Coding
34mHigh-entropy dual functions and locally decodable codes
19mError Correcting Codes for Uncompressed Messages
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
04mError-Correcting Codes: Theory and Practice
48mOutput-Compressing Randomized Encodings and Applications
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes