List Decoding of Tanner and Expander Amplified Codes...
summary
Polynomial-time list decoder up to the Johnson bound for Tanner/expander codes with inner distance delta0 and graph spectral gap lambda, achieving decoding up to the Johnson radius of the design distance (roughly delta0 − lambda). Construction uses a geometric covering lemma via L2 minimization then a relaxation to SOS pseudo-distributions with PSD moment matrix plus random conditioning and rounding; runtime is currently large (n^{Θ(1/η^2)} from conditioning on 1/η^2 coordinates) but the algorithm succeeds and extends to AEL‑amplified and larger‑alphabet codes.
AI-written summary · about
chapters (9)
- 0:00Welcome and logistics
- 4:07Coding theory fundamentals
- 7:01Tanner codes and results
- 11:07Techniques and covering
- 15:57Proving the Johnson bound
- 23:41Distance and relaxation
- 33:30Pseudo code word analysis
- 41:20Extensions and future work
- 46:26Closing discussion
related talks
01h 09mWhen Cryptography Meets Modern Channel Coding
41mHigh-Rate Fair-Density Parity-Check Codes
01h 06mAlgorithms for the k-List Problems
19mError Correcting Codes for Uncompressed Messages
37mSuccinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
34mHigh-entropy dual functions and locally decodable codes
01h 02mTree PCPs