Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
summary
Shows explicit codes (univariate multiplicity and folded Reed–Solomon) that are list-decodable up to capacity and whose decoding runs in n·polylog n time. Method builds the usual interpolation polynomial linear in the y-variables, models the interpolation as an Fx-module / polynomial-matrix shortest-vector problem (Alekhnovich-style) to get a low-degree q, then solves the resulting linear differential system by a divide-and-conquer doubling (FFT-like) to recover an affine subspace of solutions. Parameters: s = Θ(1/ε²), m = Θ(1/ε); multiplicity case needs large characteristic; final pruning to constant-size list uses KRSW randomized step.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 1:24Nearly linear time algorithms
- 3:54Randomized vs deterministic
- 5:40Reed-Solomon history
- 11:36Folded RS and multiplicity codes
- 13:24Univariate multiplicity codes
- 16:33List-decoding main results
- 20:11Proof techniques overview
- 23:10Linear algebra for decoding
- 31:31Interpolation details
- 38:11Short vectors in modules
- 44:36Differential equation solving
- 49:59Nearly linear time steps
- 51:08Summary and future
related talks
41mHigh-Rate Fair-Density Parity-Check Codes
01h 06mAlgorithms for the k-List Problems
01h 09mWhen Cryptography Meets Modern Channel Coding
19mError Correcting Codes for Uncompressed Messages
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
01h 00mError-Correcting Codes That Enable Efficient SNARKs
34mHigh-entropy dual functions and locally decodable codes
58mBosonic (And Other) Codes With Interesting Logical Gate Sets