Deletion Codes in the High-noise and High-rate Regimes
summary
Constructs explicit deletion codes using explicit concatenated construction that pairs a Reed-Solomon outer + dense inner code with small constant headers or zero buffers so block boundaries can be recovered and outer decoding finishes the job. Claims an efficient encoder/decoder that achieves constant rate against 1−ε deletions with alphabet size ≈1/ε^3 and a separate binary construction that achieves high rate while correcting a constant deletion fraction (existential bound ~0.17 known). Also obtains list decoding up to 1/2 deletions with polynomial list size.
AI-written summary · about
chapters (17)
- 0:00Introduction
- 0:27Erasers
- 3:52Deletions are easy
- 4:56What is known
- 8:33What is possible
- 10:45What we get
- 11:32Concatenation
- 13:59Decoding
- 15:51High deletions
- 16:36Constant size headers
- 21:34The algorithm
- 22:36Bounded budget
- 25:18Highrate binary codes
- 26:26Buffers
- 27:10Inner Decoder
- 27:38Deletions
- 29:53Questions
related talks
01h 14mPolar Codes III
40mTutorial on Capacity in Coding for Interactive Communication (Part 2 of 2)
32mMust One Learn the Channel to Communicate at Capacity?
47mHardness Amplification and the Approximate Degree of Constant-Depth Circuits
23mDeduBB: Binary Code Size Reduction via Post-Link Basic Block Deduplication
06mVerified Reversible Programming for Verified Lossless Compression
19mCode Size Reduction Deep Dive: Zc Extensions and Dictionary Compression Custom Instruction
01h 04mExplicit SoS Lower Bounds from (Small-Set) High Dimensional Expanders