🔢 mathematics

List-Decoding Counterexamples Yield Lower Bounds on Mutual Correlated Agreement Error

This paper demonstrates that explicit counterexamples to list-decodability can be constructively transformed into codes with provably high mutual correlated agreement error, thereby establishing a direct link between list-decoding failures and lower bounds on this specific error metric for algebraic-geometry and Reed-Solomon codes.

Original authors: Yiwen Gao, Hong Yang, Yang Xu, Haibin Kan

Published 2026-07-14

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Yiwen Gao, Hong Yang, Yang Xu, Haibin Kan

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 a detective trying to catch a group of spies (codewords) who are trying to sneak past a security checkpoint (a code). In the world of digital communication, these "spies" are actually messages that have been slightly scrambled by noise. Usually, if a message is too far from the correct pattern, the security system says, "Nope, that's not a valid message," and throws it out.

But sometimes, things get tricky. Imagine a scenario where a single scrambled message is suspiciously close to many different valid spy patterns at once. In the world of coding theory, this is called a list-decoding counterexample. It's like finding a suspect who fits the description of five different people in the crowd. If this happens, the standard security check might get confused and say, "Well, maybe this is one of them," when it shouldn't.

This paper, written by Yiwen Gao, Hong Yang, Yang Xu, and Haibin Kan, tackles a specific, high-stakes version of this problem. They are looking at a security test called Mutual Correlated Agreement. Think of this test as a way to check if a whole group of scrambled messages, when mixed together randomly (like blending five smoothies into one), will still look like a valid spy pattern.

The Big Discovery: The "Bad Mix" Recipe

The authors prove a very specific, constructive fact: If you can find a list-decoding counterexample (a message that looks like too many valid codes), you can use it to build a new, slightly different code that is guaranteed to fail the "Mutual Correlated Agreement" test.

Here is the magic trick they use, explained with a kitchen analogy:

The Setup: You have a list of $L+1$ different "valid" recipes (codewords) that all taste surprisingly similar to a weird, scrambled dish (the received word).
The Extension: The authors take their original code and add one extra "ingredient" (a coordinate) to every recipe. They create two special dishes, $\pi_0$ $π_{0}$ and $\pi_1$ $π_{1}$ .
- $\pi_0$ is the original scrambled dish, but with a zero added at the end.
- $\pi_1$ is a dish that is all zeros, except for a single "1" at the very end.
The Mixing: Now, imagine mixing these two dishes together with a secret spice amount, $\alpha$ $α$ . The new dish is $\pi_0 + \alpha \cdot \pi_1$ $π_{0} + α \cdot π_{1}$ .
- On the original part of the dish, it still looks like the scrambled word.
- At the very end, it tastes exactly like the spice amount $\alpha$ .
The Trap: Because the original scrambled word was close to $L+1$ different valid recipes, there are $L+1$ specific spice amounts ( $\alpha$ values) that will make the mixed dish look perfectly like one of those valid recipes (including the new ingredient).
The Glitch: However, the two dishes $\pi_0$ and $\pi_1$ themselves don't share a common pattern with the code on this new, larger set of ingredients. This means the mixing process created a "fake" agreement that shouldn't exist.

The paper proves that if you have $L+1$ nearby codewords, you can find at least a certain number of these "bad spice amounts" (bad combining points). Specifically, the number of bad points is at least:
$\left\lceil \frac{(L+1)q}{q+L} \right\rceil$
where $q$ is the size of the "flavor palette" (the finite field).

The "Puncture and Append" Magic Trick

There's a catch. Adding that extra ingredient made the dish bigger (the code length increased). But in the real world, you can't just change the size of the message; it has to stay the same length.

The authors perform a clever "Puncture and Append" maneuver:

Puncture: They take the original code and remove one ingredient (coordinate) that doesn't break the code's structure. This makes the code slightly smaller.
Append: They add the new "bad" ingredient they found earlier.
Result: The code is back to its original size!

The paper shows that this new code, $C'$ , is almost identical to the old one. It might lose a tiny bit of "security margin" (the minimum distance decreases by at most $1/n$ ), but it is guaranteed to have a high error rate for the Mutual Correlated Agreement test. In fact, the error probability is at least:
$\frac{1}{q} \left\lceil \frac{(L+1)q}{q+L} \right\rceil$

Keeping the Shape: Structure-Preserving Codes

The authors didn't stop there. They knew that in real life, codes often have special shapes, like Reed-Solomon codes (used in CDs and QR codes) or Algebraic-Geometry (AG) codes. These codes aren't just random lists of numbers; they are built using specific mathematical maps (like evaluating polynomials at specific points).

The paper argues that you can't just throw any random ingredient into these special codes; it has to fit the recipe. The authors show that you can still perform the "Puncture and Append" trick while keeping the code's special structure intact.

For Reed-Solomon codes, you just swap one evaluation point for another.
For AG codes, you swap one "place" (a point on a geometric shape) for another.

They prove that even with these strict rules, if the original code had a list-decoding counterexample, you can build a new code in the same family that fails the Mutual Correlated Agreement test with a guaranteed error rate.

What the Paper Does NOT Say

It is important to know what this paper is not doing:

It does not say that these codes are broken for all purposes. It only shows that if a specific "list-decoding counterexample" exists, then a specific "Mutual Correlated Agreement" failure must exist.
It does not claim to fix the problem. Instead, it constructs a counterexample to show that the error probability cannot be made arbitrarily small. It's a "proof of impossibility" for making the error zero in these specific cases.
It does not suggest that this happens for every code. It only applies if you can already find a list-decoding counterexample (a message close to $L+1$ codewords).

How Sure Are They?

The authors are extremely confident. They don't just guess or simulate this on a computer. They provide a constructive proof. This means they didn't just say "it's possible"; they gave a step-by-step recipe (an algorithm) to build the new code and the specific pair of words that prove the error exists.

They explicitly state that given a received word and $L+1$ nearby codewords, the construction explicitly produces the new code and the witness words. This is a hard mathematical fact, not a suggestion.

The Takeaway for the Curious Teen

Think of this paper as a masterclass in "How to break a specific type of security test using a loophole."

The Loophole: If a message is close to too many valid codes ( $L+1$ ), the system is already in trouble.
The Break: The authors show you can use that trouble to create a "fake" valid message by mixing two other messages.
The Result: You can prove that the error rate for this mixing test is at least $1/q$ times a specific number involving $L$ and $q$ .

The paper essentially says: "If you have a list-decoding counterexample, you cannot claim that your code is perfectly safe from these mixing attacks. Here is exactly how to build the attack and how big the error will be."

For Reed-Solomon codes (the ones in your QR codes), the error lower bound becomes:
$\frac{1}{q} \left\lceil \frac{(L+1)q}{q+L(k-1)} \right\rceil$
where $k$ is the dimension of the code.

The paper concludes that the relationship between "list-decodability" and "mutual correlated agreement" is tight: if one fails, the other must fail too, and here is the exact math to prove it.

Technical Summary: List-Decoding Counterexamples Yield Lower Bounds on Mutual Correlated Agreement Error

1. Problem Statement

The paper addresses the fundamental question of Mutual Correlated Agreement (MCA) in the context of linear codes. MCA is a property critical to the soundness of batched proximity testing, a mechanism used in succinct non-interactive arguments of knowledge (SNARKs) and Interactive Oracle Proofs of Proximity (IOPPs).

Specifically, MCA investigates whether a random linear combination of received words can spuriously create a large agreement domain with a code that is not explained by the correlated agreement structure of the original words. While positive results (proximity gaps) exist for various code families up to certain bounds, there is a need to understand the limitations: specifically, how large the error probability (the likelihood of a "bad" combining point) can be when a code fails to be list-decodable.

The core problem is to establish a constructive link between list-decoding counterexamples (received words with more than $L$ codewords within a certain distance) and lower bounds on the MCA error. Previous works have shown connections between list decodability and correlated agreement, but this paper aims to provide a general, constructive method to derive explicit lower bounds on MCA error from list-decoding failures, preserving the structural properties of the code family.

2. Methodology

The authors employ a constructive approach centered on a "puncture-and-append" technique. The methodology proceeds in three logical stages:

Out-of-Domain Extension:
Starting with a linear code $C$ that is not $(p, L)$ -list-decodable, the authors identify a received word $y$ and $L+1$ distinct codewords $c_1, \dots, c_{L+1}$ within distance $p$ . They construct an extended code $C'$ of length $n+1$ by appending a new coordinate.
- Two words, $\pi_0$ and $\pi_1$ , are defined on the extended domain. $\pi_0$ carries the original received word $y$ (with a zero appended), while $\pi_1$ is zero on the original domain and 1 on the new coordinate.
- The authors utilize a linear-algebraic collision bound (Lemma 1) to select a vector $a$ (defining the appended column of the generator matrix) such that the values $m_i \cdot a^T$ (where $m_i$ are the message vectors for the nearby codewords) contain a large number of distinct values.
- Each distinct value corresponds to a "bad combining point" $\alpha$ where the linear combination $\pi_0 + \alpha \pi_1$ agrees with an extended codeword on a large set, yet does not possess correlated agreement with the original pair.
Puncture-and-Append (Length Preservation):
To ensure the resulting code has the same block length $n$ as the original, the authors puncture (remove) one coordinate from the original code before appending the new one.
- They prove that if the original code is not $(p, L)$ -list-decodable, there exists a coordinate whose removal preserves the dimension and the non-list-decodability property (with a slight adjustment to the relative distance parameter).
- The "puncture one, append one" procedure yields a code $C'$ of length $n$ that retains the large set of bad combining points derived in the extension step.
Structure-Preserving Generalization:
To apply this to specific code families (like Reed-Solomon or Algebraic-Geometry codes), the authors generalize the construction to indexed code families.
- Instead of choosing an arbitrary vector for the appended column, they select an index from a finite set $\Omega$ via a map $v: \Omega \to \mathbb{F}_q^k$ .
- They introduce a collision bound $\lambda$ on the index set, ensuring that distinct messages do not collide too frequently on the available indices. This allows the construction to remain within the same code family (e.g., changing only one evaluation point in an AG code) while preserving the lower bound on MCA error.

3. Key Contributions and Results

Theorem 1 (General Linear Codes):
The paper establishes that if a linear code $C$ of dimension $k$ and length $n$ is not $(p, L)$ -list-decodable (with $p < \Delta(C) - 1/n$ ), there exists a related code $C'$ of the same length and dimension such that:
$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)q}{q+L} \right\rceil$
Furthermore, the relative minimum distance of $C'$ satisfies $\Delta(C') \geq \Delta(C) - 1/n$ . If the minimum-weight codewords of $C$ do not cover all coordinates, the distance can be preserved exactly ( $\Delta(C') \geq \Delta(C)$ ). The construction is explicit, producing both the code $C'$ and a pair of words witnessing the error.

Theorem 2 (Structure-Preserving Version):
For code families indexed by a set $\Omega$ with a column map $v$ , assuming a collision bound $\lambda$ (where any nonzero vector $u$ has at most $\lambda$ indices $\omega$ such that $u \cdot v(\omega)^T = 0$ ), the construction yields a code $C'$ within the same family.

$C'$ differs from $C$ in at most one coordinate index.
The MCA error lower bound becomes:
$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)N}{N+L\lambda} \right\rceil$
where $N = |\Omega|$ .

Corollaries for Specific Code Families:

Algebraic-Geometry (AG) Codes: By setting $\Omega$ as the set of rational places and $\lambda = \deg(G)$ , the authors show that if an AG code is not list-decodable, one can modify the evaluation divisor $D$ by changing at most one place to obtain a code with the specified MCA error lower bound. The resulting code remains over the same function field and Riemann-Roch space.
Reed-Solomon (RS) Codes: As a specialization where $\Omega = \mathbb{F}_q$ and $\lambda = k-1$ (degree of polynomials), the result yields an error lower bound of $\frac{1}{q} \lceil \frac{(L+1)q}{q+L(k-1)} \rceil$ . This confirms that list-decoding failures in RS codes directly imply significant MCA errors.

4. Significance and Claims

The paper claims to provide a constructive and general method for translating list-decoding counterexamples into lower bounds on mutual correlated agreement error.

Contrast with Prior Work: The authors note that previous works (e.g., Ben-Sasson et al., Crites and Stewart) derived similar lower bounds for Reed-Solomon codes using specific operations like division by $X-\beta$ , which inherently shifted the degree of the code (from $k$ to $k+1$ ). In contrast, this paper's construction preserves the code dimension and block length, and applies to arbitrary linear codes without requiring degree shifts.
Structural Integrity: A significant contribution is the ability to maintain the code's structural family (e.g., keeping an AG code as an AG code over the same space) while only modifying a single coordinate. This is crucial for applications where the code family is fixed by the underlying algebraic structure.
Soundness Implications: By explicitly constructing codes with high MCA error from list-decoding failures, the paper quantifies the limits of soundness in batched proximity testing. It demonstrates that if a code is not list-decodable, one cannot guarantee that random linear combinations will remain far from the code with high probability; specifically, the error probability is bounded below by the derived formula.

The work does not propose new experimental protocols or future applications beyond instantiating the principle for AG and RS codes. Its primary contribution is theoretical: establishing a rigorous, constructive bridge between list-decoding properties and mutual correlated agreement error bounds.