Deterministic Rateless Codes for BSC
summary
Explicit rateless construction for the binary symmetric channel that outputs a systematic infinite generator matrix whose next row is computed deterministically by an exponential‑time search, inner blocks of logarithmic length use ML decoding, and an outer Guruswami–Indyk outer code boosts rate to near one. Weight distribution is forced to match the random code average via bin splitting, marking small bins, and pairwise independence / Chebyshev splitting, yielding capacity for any constant p in (0,1/2) and almost‑exponential decay of decoding error.
AI-written summary · about
chapters (8)
- 0:00Start
- 4:47Concatenated Codes
- 10:34Maximum Likelihood Decoding
- 16:27Exponential Time Algorithm
- 22:33Chebyshev's Inequality
- 27:31Weight Distribution
- 28:11Open Problems
- 29:58Extend this Construction to Other Binary Memoryless Symmetric Channels
related talks
01h 14mPolar Codes III
40mTutorial on Capacity in Coding for Interactive Communication (Part 2 of 2)
22mRandom Variate Generation with Formal Guarantees
32mMust One Learn the Channel to Communicate at Capacity?
20mBit Blasting Probabilistic Programs
22mComplexity and Applications of Random Circuit Sampling
29mApproximating the Permanent of Positive Semidefinite Matrices
01h 01mTrue Complexity of Multilinear Systems