List Decoding Capacity and Algorithmic Error Correction Limits

This direction is split into other directions: interleaved decoding, exponential list size growth. Its last version stays readable and citable here.

Version 1 of 1130 papers191 conceptsfrozen 2026-10-04

In classical coding theory, the goal is simple: recover a message from a noisy signal. For decades, this was synonymous with unique decoding. If a code has a minimum distance $d$, a unique decoder can guaranteed-correct any pattern of up to $d/2$ errors. This threshold, known as the unique decoding radius, represents a hard wall. If the noise exceeds this limit, the received signal might sit exactly halfway between two valid codewords, making it mathematically impossible to pick the "right" one.

However, the information-theoretic limit of a channel—its capacity—often lies far beyond this $d/2$ wall. To bridge this gap, researchers have turned to list decoding. Instead of demanding a single answer, a list decoder outputs a small set of all possible codewords within a given radius. If the list size remains small (ideally polynomial in the code length), the "true" message is almost certainly among them.

Reaching the Information-Theoretic Limit

The ultimate prize in this field is "list decoding capacity." For a code with rate $R$, the information-theoretic limit for error correction is a fraction of errors approaching $1-R$. Traditional unique decoding is stuck at $(1-R)/2$.

Atri Rudra and Venkatesan Guruswami achieved a landmark breakthrough in Explicit Codes Achieving List Decoding Capacity by introducing Folded Reed-Solomon codes. By bundling consecutive symbols of a standard Reed-Solomon code into single symbols over a larger alphabet, they showed it is possible to recover data even when the error rate effectively doubles the unique decoding limit, hitting the $1-R$ capacity.

Breaking the Johnson Bound

Before reaching capacity, decoders often encounter the Johnson bound, a theoretical "soft" limit that suggests list decoding is only efficient up to a certain radius determined by the code's distance. For many years, it was unclear if standard algebraic codes could ever surpass this.

Recent work has shattered this ceiling using higher-order algebraic structures. In Decoding Multivariate Multiplicity Codes on Product Sets, Siddharth Bhandari, Mrinal Kumar, and Prahladh Harsha demonstrated that by evaluating not just a polynomial, but also its partial derivatives (multiplicities), one can list-decode all the way up to the code's distance. This "multiplicity" approach provides more "hooks" for the decoder to latch onto, allowing it to navigate much higher noise levels than the Johnson bound would predict.

Similarly, Atri Rudra and Mary Wootters showed in Every list-decodable code for high noise has abundant near-optimal rate puncturings that most Reed-Solomon codes are actually much more robust than previously thought. They proved that random "puncturing" (sampling) of these codes allows them to beat the Johnson bound, suggesting that the bottleneck was often in our analysis, not the codes themselves.

The Geometry of Noise and List Sizes

Why does list decoding eventually fail? The answer lies in the geometry of the code space. As the decoding radius increases, the "volume" of the sphere around a received signal grows. Eventually, this sphere contains an exponential number of codewords, making it impossible to output a "short" list in polynomial time.

Antonia Wachter-Zeh explored these limits for rank-metric codes in Bounds on List Decoding Gabidulin Codes, establishing that beyond the Johnson radius, the number of potential codewords explodes. This creates a fundamental mathematical "speed limit."

In the extreme "zero-rate" regime, where we have very few messages but very long codewords, Boris Bukh and Yury Polyanskiy found a surprising combinatorial "hiccup." In List-Decodable Zero-Rate Codes, they showed that the maximum error radius behaves differently depending on whether the allowed list size is even or odd, revealing deep connections between coding theory and Ramsey theory.

Algorithmic Efficiency and Field Sizes

Building a code that can be list-decoded is only half the battle; the other half is doing it efficiently.

One major hurdle is the alphabet size. Reaching the Singleton bound for list decoding often requires symbols from a massive field. Joshua Brakensiek and Manik Dhar addressed this in Improved Field Size Bounds for Higher Order MDS Codes, proving that while exponential field sizes are sometimes necessary to reach the absolute limit, we can now construct explicit codes that approach these limits more efficiently than ever before.

On the speed front, researchers are pushing toward linear-time decoding. Xin Li and colleagues have focused on expander codes, which use the sparsity of expander graphs to perform ultra-fast error correction. In Improved Decoding of Expander Codes, they narrowed the gap between the theoretical minimum distance and the number of errors that can be resolved in linear time, bringing us closer to decoders that are both optimal and blazingly fast.

New Frontiers: From Synchronization to Cryptography

The principles of list decoding are now being exported to more complex error models.

  • Synchronization Errors: Bernhard Haeupler and Venkatesan Guruswami have redefined the limits for codes that handle insertions and deletions (insdel errors), establishing the "Half-Singleton bound" in Efficient Linear and Affine Codes for Correcting Insertions/Deletions.
  • Semi-Adversarial Noise: Joshua Brakensiek and Manik Dhar introduced models in Unique Decoding of Reed-Solomon and Related Codes for Semi-Adversarial Errors that sit between random and worst-case noise, showing that unique decoding can actually reach capacity if the adversary is slightly constrained.
  • Post-Quantum Security: The compact nature of these advanced codes is being leveraged to build new cryptosystems, such as the LowMS KEM by Nicolas Aragon and Antonia Wachter-Zeh, which uses rank-metric codes to reduce key sizes in a post-quantum world.

Papers in this version

Showing 60 of 130 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_list_decoding_capacity_and_algorithmic_e_7716433f,
  title = {List Decoding Capacity and Algorithmic Error Correction Limits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/list-decoding-capacity-and-algorithmic-error-correction-limits/rdr_7716433fbb714574874ff68d560ca06e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_list_decoding_capacity_and_algorithmic_e_7716433f_v1,
  title = {List Decoding Capacity and Algorithmic Error Correction Limits},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/list-decoding-capacity-and-algorithmic-error-correction-limits/rdr_7716433fbb714574874ff68d560ca06e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}