Gilbert and Varshamov meet Johnson: List Decoding Nearly-Optimal Binary Codes
summary
Gives an explicit algorithm that list-decodes Ta‑Shma’s near–Gilbert–Varshamov binary code to the Johnson bound, proving recovery from a (1−ρ)/2 error fraction whenever ρ ≥ √ε. Builds a Lasserre SDP whose variables are local pseudo‑distributions, applies SDP rounding to an actual distribution, and analyzes it by bias‑amplification of random‑walk XOR codes plus expander mixing. Runtime is poly(n) but exponential in 1/ε; the decoder succeeds with the Johnson‑bound list size.
AI-written summary · about
chapters (8)
- 0:00Error correcting codes motivation
- 3:39Ta-Shma’s code to Johnson bound
- 10:41SDP decoding algorithm
- 14:31Bias amplification in expander graphs
- 21:39Random walk XOR codes properties
- 23:45Decoding random walk XOR with SDP
- 30:54Lasserre SDP decoding analysis
- 33:06Open questions and future
related talks
41mHigh-Rate Fair-Density Parity-Check Codes
01h 09mWhen Cryptography Meets Modern Channel Coding
34mPrivate Information Retrieval: Chasing Capacity with Algebraic Codes
58mBosonic (And Other) Codes With Interesting Logical Gate Sets
01h 00mError-Correcting Codes That Enable Efficient SNARKs
04mError-Correcting Codes: Theory and Practice
19mError Correcting Codes for Uncompressed Messages
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics