Deletion-Correcting Codes and Trace Reconstruction
Stub. Codes correcting deletions rather than substitutions (Varshamov-Tenengolts codes, the classical single-deletion-correcting construction); the trace reconstruction problem — recovering an unknown string from many independently-deleted ("traced") noisy copies of it — and its coded variant, where the sender may choose the original string to make reconstruction easier; and the related problem of designing strings that avoid certain forbidden substrings, using string correlation.
Corresponds to Lecture topics 8 and 13. A substitution error leaves a string’s length unchanged; a deletion doesn’t, which breaks the usual coordinate-by-coordinate distance arguments entirely and needs its own theory. The Varshamov-Tenengolts codes are the classical single- deletion-correcting construction (a simple weighted-sum check that, remarkably, corrects exactly one deletion with close to the information-theoretically optimal redundancy). Trace reconstruction asks a statistical question in the same spirit: given many independent, randomly-deleted (“traced”) copies of an unknown string, how many traces are needed to reconstruct it with high probability — and the coded variant lets the sender choose the transmitted string from a reconstruction-friendly code rather than facing an arbitrary worst-case string, dramatically reducing the number of traces needed. String correlation and avoiding forbidden substrings is the combinatorial tool underlying good constructions for both problems. This machinery is the direct prerequisite for molecular-and-dna-storage-coding, where deletion/insertion errors (not substitutions) are the dominant noise type.
Outline (TODO — flesh out each)
- Single-deletion-correcting codes — Varshamov-Tenengolts codes
- The trace reconstruction problem
- Coded trace reconstruction
- String correlation and avoiding forbidden substrings
- Coded string reconstruction