The Insertion List-Decoding Capacity and an Improved Bound on the Deletion List-Decoding Capacity

What the math gives to ML

The paper identifies an explicit entropy-controlled construction for binary codes that remain polynomial-list-decodable under a positive fraction of insertions: a symmetric two-state Markov code ensemble achieves rate $(1+\delta)(1-h(\delta/(1+\delta)))$. The transferable asset is correlated sequence generation for robustness to unknown alignment, rather than treating token corruption independently. This suggests synchronization-robust neural representations: generate latent token streams with a tunable Markov prior, train a decoder against insertion perturbations, and use the capacity expression to select a conservative latent rate. The deletion result is mainly a design warning: Markov correlation that helps insertion robustness should not automatically be expected to improve deletion robustness.