🔢 mathematics

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

This paper establishes the exact capacity for list-decoding binary codes from a $\delta$ -fraction of insertions as $(1+\delta)(1-h(\frac{\delta}{1+\delta}))$ using symmetric 2-state Markov chains, while also demonstrating that this approach does not improve upon random coding for deletions and providing a tighter upper bound on deletion list-decoding capacity that matches the asymptotic behavior of the binary deletion channel.

Original authors: Roni Con, Dean Doron, João Ribeiro

Published 2026-07-07

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Roni Con, Dean Doron, João Ribeiro

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are sending a secret message written on a long strip of paper. The message is just a string of 0s and 1s. Now, imagine a mischievous gremlin is tampering with your message as it travels. This gremlin has two ways to mess things up:

Insertions: The gremlin sneaks in extra 0s or 1s, making the message longer.
Deletions: The gremlin rips out some 0s or 1s, making the message shorter.

This is the world of synchronization errors. Unlike a simple typo where a letter is just wrong (like an "A" becoming a "B"), here the entire rhythm of the message gets thrown off. The receiver doesn't know where the errors happened, only that the length has changed.

In the world of coding theory, we want to know: How much information can we pack into a message so that, even after the gremlin messes with it, we can still figure out what the original message was?

Usually, we try to find the one original message. But sometimes, the damage is so bad that we can't be 100% sure which one it was. So, we use a strategy called List-Decoding. Instead of demanding a single answer, we say, "Give me a short list of possible original messages. As long as the real one is on that list, we're good."

The paper you provided, "The Insertion List-Decoding Capacity and an Improved Bound on the Deletion List-Decoding Capacity," by Roni Con, Dean Doron, and João Ribeiro, solves a long-standing puzzle about how big that list needs to be and how much information we can send.

Here is the breakdown of their findings using simple analogies:

1. The "Insertion" Puzzle: Solving the Mystery of Extra Bits

The Problem: When the gremlin adds bits (insertions), how much data can we send?
The Old Thinking: For a long time, scientists had a "best guess" (a lower bound) based on picking messages completely at random. They also had a "worst-case limit" (an upper bound) based on simple math. But for high error rates (when the gremlin adds a lot of bits), the guess and the limit were far apart. It was like knowing the treasure is somewhere in a huge forest, but not knowing if it's in the north or the south.

The New Discovery:
The authors found the exact answer. They proved that the maximum amount of data you can send (the "capacity") is exactly equal to that "worst-case limit" everyone already knew.

The Analogy: Imagine you are trying to fit a long rope into a box. You thought you could only fit a short piece in. The authors proved, "No, you can actually fit the entire box's worth of rope, no more and no less."
How they did it: They didn't just pick random messages. They picked messages that followed a specific pattern, like a "Markov chain." Think of this as a message where the next bit depends on the previous one (like a conversation where the next word depends on the last one). They showed that if you generate your messages using this specific "rhythmic" pattern, you can perfectly hit that theoretical limit.

2. The "Deletion" Puzzle: The Gremlin Who Rips Bits Out

The Problem: When the gremlin removes bits (deletions), how much data can we send?
The Old Thinking: Scientists knew that random messages worked okay up to a certain point. They also knew that for "Insertion" errors, using those rhythmic "Markov" patterns was a superpower. So, they naturally asked: "If rhythmic patterns help with insertions, maybe they help with deletions too?"

The New Discovery (The Twist):
The authors tested this idea and found a surprising dichotomy (a split personality).

The Result: For deletions, using those rhythmic "Markov" patterns does absolutely nothing to improve things compared to just picking random messages.
The Analogy: Imagine you are trying to find a lost key in a messy room.
- For Insertions (extra junk added), using a specific flashlight (the Markov pattern) helps you find the key much better than a random sweep.
- For Deletions (pieces missing), that same special flashlight is useless. A random sweep works just as well. The authors proved mathematically that no matter how you tune that "Markov" pattern, you can't beat the performance of pure randomness for deletions.

3. The "Small Deletion" Limit: A Sharper Ruler

The Problem: What happens when the gremlin only rips out a tiny amount of bits?
The Old Thinking: We knew the general shape of the answer, but the details for very small errors were fuzzy.

The New Discovery:
The authors created a new, sharper "ruler" (an upper bound) for this specific scenario.

The Result: They showed that when the error rate is very small, the capacity behaves almost exactly like a famous formula from the 1940s (Shannon's capacity for bit flips).
The Analogy: If you are measuring a tiny scratch on a car, a rough estimate isn't good enough. The authors built a micrometer. They proved that for tiny deletions, the limit is extremely close to what we expect from standard noise, differing only by a tiny, almost invisible amount.

Summary of the "Big Picture"

This paper is like a cartographer finally drawing the perfect map of a dangerous territory.

For Insertions: They found the exact border. You can send data up to a specific limit, and they showed you exactly how to generate the messages to hit that limit (using rhythmic patterns).
For Deletions: They proved that the "rhythmic pattern" trick doesn't work here. Randomness is just as good as any fancy pattern.
For Tiny Deletions: They refined the map to show that the limits are very close to what we already suspected for small errors.

Why does this matter?
In the world of coding, knowing the exact limit is crucial. It tells engineers, "Stop trying to invent better codes for this specific problem; you've reached the theoretical ceiling." It saves time and effort by confirming that the current best methods are actually the best possible methods.

The paper does not discuss medical uses, future AI applications, or commercial products. It is purely a mathematical proof about the fundamental limits of sending information through a noisy, shifting channel.

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

Problem Statement

The paper investigates the list-decoding capacity of binary codes under adversarial synchronization errors, specifically focusing on insertions and deletions. Unlike bit-flip or erasure channels, where the list-decoding capacity is well-understood and coincides with the Shannon capacity of the corresponding probabilistic channel, the capacity for synchronization errors remains poorly understood.

The central question is: What is the largest rate $R$ at which a family of binary codes can be list-decoded from a $\delta$ -fraction of insertions or deletions with a list size $L$ that is polynomial in the block length $n$ ?

Prior to this work, the state of knowledge was limited:

Deletions: The best known lower bound was $1 - h(\delta)$ , achieved by uniformly random codes. The upper bound was loose ( $1 - 2\delta$ ).
Insertions: For $\delta \leq 1/2$ , the lower bound was also $1 - h(\delta)$ . For $\delta > 1/2$ , only a tiny positive lower bound was known, while the upper bound was $(1+\delta)(1 - h(\frac{\delta}{1+\delta}))$ .
Gap: There was a significant gap between lower and upper bounds, particularly for insertions where $\delta > 1/2$ , and it was unknown if structured random codes (e.g., Markov chains) could outperform uniformly random codes for deletions.

Methodology

The authors employ probabilistic methods, specifically analyzing the performance of random codes sampled with memory (Markov chains) versus uniformly random codes.

Markov Chain Sampling: Instead of sampling codewords bit-by-bit independently (uniformly random), the authors sample codewords according to a symmetric order-1 Markov chain. This introduces correlation between adjacent bits, controlled by a parameter $\alpha$ (the probability that $X_i = X_{i-1}$ ).
Large Deviations Theory: To analyze the probability that a random codeword contains a specific received string as a subsequence (for deletions) or supersequence (for insertions), the authors utilize Cramér's theorem and the Lagrange-Fenchel transform of moment-generating functions. This allows them to derive precise asymptotic bounds on the probability of "bad" events (i.e., a received string being a subsequence of too many codewords).
Combinatorial Counting (Runs): For the upper bound on deletion capacity, the authors analyze the number of "runs" (maximal contiguous blocks of identical symbols) in codewords. They use a pigeonhole principle argument combined with bounds on the size of deletion balls (Levenshtein bounds) to show that high-rate codes must contain codewords with many runs, which in turn forces the existence of received strings with large list sizes.

Key Contributions and Results

1. Exact Capacity of List-Decoding from Insertions

The paper establishes the exact list-decoding capacity for insertions, denoted $C_{ins}(\delta)$ , for all $\delta \in [0, 1]$ .

Result:
$C_{ins}(\delta) = (1 + \delta) \left( 1 - h\left( \frac{\delta}{1 + \delta} \right) \right)$
Achievability: This capacity is achieved with high probability by a code sampled from a symmetric order-1 Markov chain with a carefully chosen transition probability $\alpha = \frac{1+\delta}{2}$ .
Significance: This result closes the gap for insertions. It improves upon the previous lower bound of $1-h(\delta)$ (valid only for $\delta \leq 1/2$ ) and the tiny positive lower bound for $\delta > 1/2$ . It matches the previously known averaging-based upper bound, proving it is tight. The construction guarantees a constant list size $L = O(1/\epsilon)$ for rates below capacity.

2. Limitations of Markov Codes for Deletions

The authors investigate whether the success of Markov chains for insertions extends to deletions.

Result: Order-1 Markov codes do not outperform uniformly random codes for list-decoding from deletions.
Theorem: For any fraction of deletions $\delta \in [0, 1/2]$ and any rate $R > 1 - h(\delta)$ , a code sampled from an order-1 Markov chain will, with high probability, contain a received string $y$ that is a subsequence of an exponential number of codewords ( $2^{\Omega(\epsilon n)}$ ).
Significance: This reveals a dichotomy between insertions and deletions. While memory (Markov structure) helps achieve the optimal capacity for insertions, it provides no advantage over uniform randomness for deletions in the list-decoding regime.

3. Improved Upper Bound for Deletion Capacity

The paper provides a new, sharper upper bound on the list-decoding capacity for deletions, $C_{del}(\delta)$ , specifically for small $\delta$ .

Result:
$C_{del}(\delta) \leq 1 - \delta - (\gamma - \delta)h\left( \frac{\delta}{\gamma - \delta} \right) = 1 - h(\delta) + o(\delta)$
where $\gamma = \frac{1}{2} - \sqrt{\frac{h(\delta) \ln 2}{2}}$ .
Asymptotic Behavior: As $\delta \to 0$ , the capacity behaves as $1 - h(\delta) + o(\delta)$ .
Significance: This matches the asymptotic behavior of the capacity of the probabilistic deletion channel (where bits are deleted with probability $\delta$ ). This suggests that, for small deletion fractions, the adversarial list-decoding capacity and the probabilistic channel capacity share the same leading-order behavior, despite the adversarial nature of the errors.

Significance and Claims

The paper claims to make fundamental progress in understanding the limits of synchronization error correction:

Resolution of the Insertion Problem: By determining the exact capacity for insertions, the authors resolve a long-standing open problem. They demonstrate that the "averaging bound" is tight and achievable via Markovian random coding.
Separation of Models: The work highlights a fundamental difference between insertion and deletion errors. The techniques that optimize insertion capacity (introducing memory via Markov chains) are ineffective for deletions, where uniform randomness remains optimal among the class of order-1 Markov codes.
Connection to Probabilistic Channels: The improved upper bound for deletions aligns the adversarial list-decoding capacity with the probabilistic deletion channel capacity in the low-noise regime, providing a deeper theoretical link between adversarial and probabilistic error models.

The authors emphasize that their results for insertions are non-constructive (based on the existence of random codes) but provide the first proof that the capacity is strictly higher than $1-h(\delta)$ for $\delta > 1/2$ . For deletions, the work primarily refines the upper bounds and characterizes the limitations of specific random coding strategies.