Coding Theory in Almost Linear Time and Sublinear Space
summary
Constructs asymptotically good codes that achieve deterministic encoding or deterministic decoding in n^{1+o(1)} time while using sublinear space, splitting the results into a hashing based encodable construction (explicit, with a lower bound showing random access is necessary) and a decoding construction built from locally correctable codes plus a new derandomization called iterative correction. Claims are concrete: order n randomness strings suffice, each iteration inspects n^{α} rows giving total time n^{1+α}, and the method succeeds for standard LCC parameters.
AI-written summary · about
chapters (8)
- 0:00Introduction
- 1:25Complexity Theory
- 10:45Locally decodable codes
- 14:10Terministic decoding
- 20:58Randomness in computation
- 28:07Uniform Decoder
- 28:49Locally Correctable Codes
- 31:06iterative correction
related talks
37mSuccinct Randomized Encodings from Laconic Function Evaluation, Faster and Simpler
01h 09mNoisy Connections: A Survey of Interactive Coding and Its Borders with Other Topics
01h 09mWhen Cryptography Meets Modern Channel Coding
41mHigh-Rate Fair-Density Parity-Check Codes
19mError Correcting Codes for Uncompressed Messages
04mError-Correcting Codes: Theory and Practice
48mOutput-Compressing Randomized Encodings and Applications
32mTime-Lock Puzzles from Randomized Encodings