🔢 mathematics

Average-Radius List-Decodability of Random Linear Codes

This paper proves that random linear codes over any alphabet $\mathbb{F}_q$ achieve the optimal rate for average-radius list-decoding with a list size of $O(1/\epsilon)$ , thereby extending previous results known only for binary linear codes and general non-linear codes to the broader setting of linear codes over arbitrary prime power alphabets.

Original authors: Venkatesan Guruswami, Shilun Li, Mihir Singhal

Published 2026-08-25

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Venkatesan Guruswami, Shilun Li, Mihir Singhal

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

In the vast landscape of digital communication, where messages travel across oceans and through satellites, the safety of information relies on a delicate balance between speed and protection. To send data reliably, engineers add extra bits of information to the original message, creating a safety net that allows the receiver to spot and fix errors caused by noise or interference. This process is known as error correction. However, when the noise is severe, a single "best guess" at the original message often fails. Instead, modern systems use a strategy called list decoding, where the receiver generates a short list of possible original messages, one of which is guaranteed to be the correct one. The goal for researchers is to find codes that can handle the maximum amount of noise possible while keeping this list of candidates as short as possible, ensuring the system remains efficient.

For decades, mathematicians have studied random codes—collections of messages chosen by chance—to understand the theoretical limits of this process. They discovered that a random selection of messages could handle a specific amount of noise with a very short list. But real-world systems rarely use purely random codes; they prefer linear codes, which have a structured, mathematical pattern that makes them easier to store and process. While it was known that these structured codes could also handle high noise, a critical question remained: could they do so with the same short list size as the random ones, or would the structure force the list to grow much larger? Furthermore, researchers had developed a stricter, more robust version of list decoding called average-radius decoding. This method demands that the entire group of candidate messages, on average, stays far enough away from the noisy signal to ensure reliability, rather than just checking if the single worst candidate is far enough away. It was unclear whether the structured linear codes could meet this stricter standard with the same efficiency.

A team of researchers at the University of California, Berkeley, has now settled this question with a definitive proof. They demonstrated that random linear codes, the structured kind used in practical applications, are just as powerful as their purely random counterparts when it comes to this stricter form of decoding. Specifically, they proved that for any fixed alphabet size and any level of noise below a certain threshold, a random linear code can be decoded with a list size that grows only inversely with the distance from the maximum capacity. In simpler terms, as the system gets closer to its theoretical limit, the number of candidates needed to find the right message grows in a predictable, manageable way, matching the performance of the best possible random codes. This result confirms that the mathematical structure of linear codes does not come at the cost of decoding efficiency, even under the most demanding conditions.

The researchers arrived at this conclusion by analyzing how these codes behave when a noisy signal is received. In the standard approach to list decoding, mathematicians often look at the worst-case scenario: they check if the single closest message in a group is too far from the center. The new work, however, focused on the average distance of the entire group of candidates. The team showed that for random linear codes, the average distance of the closest messages to the received signal is always large enough to guarantee success. They achieved this by developing a new way to count and analyze the relationships between the messages in the code. Instead of relying on geometric arguments that worked for simple random codes but failed for structured ones, they used a method based on the total "deficit" of the messages—how much closer they are to the center than the limit allows. By proving that a small group of independent messages cannot collectively be too close to the center, they showed that the average distance of the nearest neighbors must remain high.

This finding is significant because it removes a major uncertainty in the design of error-correcting systems. Previously, the best known methods for proving that linear codes could handle high noise with short lists resulted in list sizes that were much larger than necessary, or they only worked for specific types of codes like binary ones. The new proof applies to codes over any alphabet size and achieves the optimal list size, matching the theoretical best. The authors established that the probability of a random linear code failing to meet this standard is vanishingly small, effectively zero for any practical system size. This means that engineers can confidently rely on these structured codes to operate at the very edge of what is theoretically possible without worrying that the decoding process will become unmanageably complex.

The work also clarifies the relationship between different types of decoding guarantees. While it was known that a code capable of standard list decoding could be adapted to the average-radius version, doing so usually required a much larger list of candidates. The new result shows that for random linear codes, this penalty is not necessary; the same short list that works for the standard version also works for the stricter average-radius version. This unification suggests that the structural properties of linear codes are robust enough to handle the most rigorous definitions of reliability. The researchers noted that while their proof establishes the existence of these optimal codes, the specific constants involved in the list size can be quite large, leaving open the question of whether a tighter, more precise bound can be found. Nevertheless, the core finding stands: the structured codes used in the real world are just as capable as the theoretical ideal.

In the broader context of information theory, this result reinforces the idea that randomness and structure are not opposing forces in the quest for reliable communication. The study confirms that the mathematical patterns inherent in linear codes do not hinder their ability to recover from severe corruption. By proving that these codes achieve the same efficiency as purely random ones, the research provides a solid theoretical foundation for future advancements in data transmission. The authors conclude that the gap between what is theoretically possible and what can be achieved with structured codes has been closed for this specific problem, offering a clear path forward for designing more robust communication systems. The proof stands as a rigorous confirmation that the best possible performance is within reach for the codes that power our digital infrastructure.

Technical Summary: Average-Radius List-Decodability of Random Linear Codes

Problem Statement
This work addresses the combinatorial list-decodability of random linear codes over finite fields $\mathbb{F}_q$ at rates approaching the list-decoding capacity. Specifically, it investigates the average-radius list-decodability property, a stronger variant of standard list-decoding.

While standard $(p, L)$ -list-decodability requires that no Hamming ball of radius $pn$ contains more than $L$ codewords, average-radius $(p, L)$ -list-decodability demands that for any center $y \in \mathbb{F}_q^n$ , the $L+1$ codewords closest to $y$ have an average fractional Hamming distance strictly greater than $p$ . This is a strictly stronger condition because the average distance is always bounded by the maximum distance.

Prior to this work, it was known that:

General random codes achieve average-radius list-decodability with list size $O(1/\epsilon)$ (Elias, 1991).
Random binary linear codes achieve this with list size $O(1/\epsilon)$ (Guruswami et al., 2021).
For non-binary random linear codes, the best known bound for average-radius list-decodability was $O(1/\epsilon^2)$ (derived from Rudra and Wootters, 2018, by applying a standard list-decoding result to the average-radius setting).

The central open question was whether random linear codes over general alphabets $\mathbb{F}_q$ could achieve the optimal $O(1/\epsilon)$ list size for average-radius list-decoding, matching the performance of general random codes and binary linear codes.

Methodology and Proof Approach
The authors adapt the proof strategy of Guruswami, Håstad, and Kopparty (GHK, 2010), which established $O(1/\epsilon)$ list-decodability for standard list-decoding of non-binary random linear codes. However, the GHK argument relies heavily on the geometric structure of Hamming balls and the fact that all considered codewords lie strictly within a fixed radius. This geometric "increasing-supports" argument fails in the average-radius setting, where codewords need only be close on average, not individually within the ball.

To overcome this, the paper introduces two new technical ingredients that replace the geometric steps of the GHK proof:

Jensen/Entropy Counting Bound (Lemma 6): Instead of bounding the number of vectors in a ball, the authors control the "total weight deficit" of a small linearly independent set. They utilize Jensen's inequality on the $q$ -ary entropy function $h_q$ to show that a linearly independent set of size $L = \Theta(1/\epsilon)$ cannot have a large total deficit (i.e., the sum of $(pn - |v|)$ for vectors $v$ in the set cannot be too large).
Greedy-Basis Argument: The authors order the nearest codewords (or elements in the span of the code and a center) by increasing weight. They greedily extract a maximal linearly independent subsequence. Using the Span-Ball Theorem (Lemma 5, adapted from GHK), they prove that this greedy basis must appear frequently throughout the ordered list. Specifically, the span of $r$ basis vectors can contain at most $O(r)$ vectors within the ball. This regularity allows the authors to transfer the deficit bound from the independent basis vectors to the entire set of nearest codewords, thereby bounding their average distance.

Key Results
The main theorem (Theorem 1) establishes the following:

Theorem: For every prime power $q$ and every $p \in (0, 1-1/q)$ , a random $\mathbb{F}_q$ -linear code of rate $R = 1 - h_q(p) - \epsilon$ is $(p, C_{p,q}/\epsilon)$ -average-radius list-decodable with probability at least $1 - q^{-\Omega(n)}$ .
Here, $C_{p,q}$ is a constant depending only on $p$ and $q$ .
This result matches the $O(1/\epsilon)$ list size achieved by general random codes and binary linear codes, resolving the gap for non-binary linear codes.

The proof relies on two lemmas:

Lemma 5 (Span-Ball Bound): With high probability, the span of any small linearly independent set of vectors inside a Hamming ball intersects the ball in only $O(|S|)$ vectors.
Lemma 6 (Deficit Bound): With high probability, no small linearly independent set in the span of the code (plus a center) has a total weight deficit exceeding $\epsilon n$ .

Significance and Claims
The paper claims to extend the GHK (2010) result for standard list-decoding to the stronger average-radius guarantee for general random linear codes, maintaining the same optimal list size of $O(1/\epsilon)$ .

Unification: It unifies the understanding of list-decodability for random linear codes across different alphabet sizes and decoding variants (standard vs. average-radius).
Overcoming Geometric Obstacles: The work demonstrates that the geometric constraints inherent in the GHK proof for standard list-decoding are not necessary for the average-radius case; instead, entropy-based counting and greedy basis extraction suffice.
Limitations: The authors note that while the list size is $O(1/\epsilon)$ , the constant $C_{p,q}$ degrades as $p \to 1 - 1/q$ (the high-noise regime). They leave open the question of whether an absolute constant $C$ (independent of $p$ and $q$ ) can be achieved, which is known for the binary case but remains open for general $q$ .

The paper does not propose new applications or experimental implementations but focuses strictly on the combinatorial properties of random linear codes, positioning the result as a fundamental advancement in probabilistic combinatorics and coding theory.

Technical Summary: Average-Radius List-Decodability of Random Linear Codes

More like this