When Relaxation Does Not Help: RLDCs with Small Soundness Yield LDCs

This paper demonstrates that any non-adaptive $q$-query relaxed locally decodable code (RLDC) with sufficiently small soundness error can be converted into a standard $q$-query locally decodable code (LDC) with comparable parameters, thereby generalizing previous separation results and yielding improved lower bounds for RLDCs, relaxed locally correctable codes (RLCCs), and probabilistically checkable proofs of proximity (PCPPs).

The Gist

Imagine you have a very long, secret message written on a giant piece of paper. However, this paper has been dropped in a muddy field, and some parts are smudged or torn (corrupted).

In the world of computer science, Locally Decodable Codes (LDCs) are like a super-powerful magnifying glass. They allow you to read just one specific letter of your secret message by looking at only a tiny, random handful of spots on the muddy paper. You don't need to read the whole thing; you just need to peek at a few spots to figure out the letter you want.

For a long time, scientists knew that if you wanted this "peeking" to work perfectly, you had to make the paper enormously long. But recently, they discovered a "cheat code" called Relaxed Locally Decodable Codes (RLDCs).

The "Cheat Code" (RLDCs)

Think of an RLDC as a slightly more forgiving magnifying glass.

• Standard LDC: "I must tell you the letter 'A' or 'B'. If I'm wrong, I fail."
• Relaxed RLDC: "I will tell you 'A', 'B', or I can say 'I give up' (represented by the symbol $\perp$)."

If the paper is too muddy to be sure, the RLDC is allowed to say, "I can't tell you the letter, but I won't guess wrong." This "give up" option is a huge relief. It turns out, with this option, you can write your message on a much smaller piece of paper while still being able to peek at it.

The Big Question

For years, researchers wondered: Is this "give up" option actually necessary?
Could it be that if you just make the "give up" rule very strict (meaning the decoder almost never says "I give up" or makes a mistake), the code automatically becomes a standard, perfect LDC?

Previous work showed this was true for very specific, simple types of codes (like linear codes), but no one knew if it held true for all complex, messy codes.

What This Paper Does

This paper says: "Yes, it holds true for everything."

The authors prove a powerful new rule: If a "Relaxed" code is so good that it almost never makes a mistake (and rarely says "I give up"), then it is secretly a "Standard" code all along.

They didn't just say "it works"; they showed you how to turn the "Relaxed" decoder into a "Standard" one.

The Analogy: The "Heavy" and "Light" Chairs

To explain their method, imagine you are trying to guess a secret number based on a group of people sitting in a room.

• The Room: The corrupted paper.
• The People: The bits of data.
• The Heavy Chairs: Some people sit in chairs that are very popular. If you pick a random group, you are very likely to pick one of these "Heavy" people.
• The Light Chairs: These are the quiet people in the back. You rarely pick them.

The authors realized that the "Heavy" people are the problem. They are the ones causing the confusion because they are queried too often.

1. The Trick: They decided to ignore the "Heavy" people entirely. They only listen to the "Light" people.
2. The Logic: Since the "Light" people are rarely picked, the chance that all of them are muddy (corrupted) is tiny.
3. The Result: By focusing only on the "Light" people, they can reconstruct the secret number perfectly. If the "Heavy" people were the only ones causing the "Relaxed" code to fail, removing them turns the code into a perfect "Standard" code.

Why This Matters

This discovery is like finding a universal key.

1. It closes a gap: It proves that you can't have a "Relaxed" code that is too good without it actually being a "Standard" code. The "Relaxed" advantage only exists if you are willing to accept a higher chance of saying "I give up."
2. It sets a limit: Because we now know that "good" Relaxed codes are just Standard codes, we can use the known limits of Standard codes to set new, stricter limits on how small these Relaxed codes can actually be.
3. It helps cryptography: These codes are used in things like secure voting and private data retrieval. Knowing their true limits helps engineers build systems that are both efficient and secure.

The Bottom Line

The paper tells us that perfection is a trap. If you try to make a "Relaxed" code (one that can say "I don't know") so perfect that it almost never fails, you accidentally force it to become a "Standard" code (one that must always guess). You can't have the best of both worlds: either you accept a few "I don't knows" to save space, or you demand perfection and pay the price in size.

Technical Summary

Here is a detailed technical summary of the paper "When Relaxation Doesn't Help: RLDCs with Small Soundness Yield LDCs" by Kuan Cheng, Xin Li, and Songtao Mao.

1. Problem Statement and Motivation

Locally Decodable Codes (LDCs) allow the recovery of any single message symbol by querying only a small number of positions in a corrupted codeword. Relaxed Locally Decodable Codes (RLDCs) are a weaker variant where the decoder is allowed to output a special failure symbol ($\perp$) instead of an incorrect symbol when the codeword is corrupted.

• The Gap: Known constructions of RLDCs achieve significantly better parameters (specifically, shorter codeword lengths $n$ for a given message length $k$ and query complexity $q$) than standard LDCs. For example, RLDCs can achieve $n = k^{1+O(1/q)}$, whereas the best known LDCs have super-polynomial length for $q > 2$.
• The Question: Is this separation fundamental? Specifically, can an RLDC with a very low "soundness error" (the probability of outputting a wrong symbol rather than $\perp$) be converted into a standard LDC?
• Prior Work:
  • It was known that 2-query RLDCs imply 2-query LDCs.
  • Recent work [GKMM25] showed that for linear codes, if the soundness error $s$ is below a threshold ($s < 2^{-\lfloor q/2 \rfloor}$), the RLDC is effectively an LDC.
  • However, it was unknown if this implication holds for nonlinear codes, which are the general case for many optimal constructions.

The Core Problem: Does a small soundness error in a general (possibly nonlinear) RLDC force it to be a standard LDC? If so, this would imply that the superior parameters of RLDCs rely entirely on having a non-negligible probability of outputting wrong symbols, rather than just outputting $\perp$.

2. Methodology and Techniques

The authors generalize and strengthen the results of [GKMM25] by removing the linearity assumption. Their approach involves a novel structural analysis of the decoder's behavior relative to specific codewords.

A. Codeword-Relative Smoothness

In linear codes, the concept of "smoothness" (whether a query set allows recovery without heavy coordinates) is independent of the specific codeword. In nonlinear codes, this is not true.

• Innovation: The authors define $(i, c)$-smoothability, where a query set $Q$ is smoothable for a specific message index $i$ and a specific codeword $c$ if the restriction of $c$ to the "light" (low-probability) coordinates uniquely determines the message bit $b_i$.
• Local Decidability: They prove that even though smoothness depends on $c$, a decoder can determine if a query set is smoothable using only local information (the values on the light coordinates and the decoder's truth table), provided the light coordinates are uncorrupted.

B. The Transformation Strategy

The authors construct a new decoder $Dec'$ from the original RLDC decoder $Dec$ as follows:

1. Heavy/Light Decomposition: Partition coordinates into "heavy" (queried with high probability) and "light" (queried with low probability).
2. Rule Derivation: For a query set $Q$ and a local view on light coordinates:
   • If the light pattern is "good" (consistent with a unique output regardless of heavy coordinates), output that symbol.
   • If the light pattern is "bad" (ambiguous or always $\perp$), output a uniformly random symbol.
3. Handling Nonsmoothable Queries: If a query set is nonsmoothable for the true codeword, the new decoder outputs a random symbol. The proof shows that the probability of sampling such a set is small if the soundness error is low.

C. Resampling Argument (The Core Proof)

To bound the probability of nonsmoothable queries, the authors use a resampling technique:

• They construct a "fake" codeword $c'$ by keeping the light coordinates of the true codeword $c$ but randomly resampling the heavy coordinates.
• If a query set $Q$ is nonsmoothable, there exists a different message $b'$ such that $c'$ (with resampled heavy bits) matches $c$ on light bits but differs on the message bit $b_i$.
• Because the heavy bits are resampled uniformly, there is a non-negligible probability that $c'$ matches the specific heavy configuration required to trigger a wrong output from the original RLDC decoder.
• Since the RLDC has low soundness error, it cannot output a wrong symbol with high probability on $c'$. This contradiction forces the probability of sampling a nonsmoothable query set to be small.

D. Imperfect Completeness

The paper extends these results to RLDCs with imperfect completeness (where the decoder might fail even on uncorrupted codewords with probability $\epsilon$). They show that such codes still yield LDCs, with the final error probability increasing additively by $\epsilon$.

3. Key Contributions and Results

1. Generalization to Nonlinear Codes

Theorem 1.4: Any $q$-query RLDC with perfect completeness and soundness error $s < 2^{-q}$ (for binary alphabet) is also a $q$-query LDC with comparable parameters.

• This removes the linearity requirement from [GKMM25], proving that the "relaxation" in RLDCs is only beneficial if the soundness error is relatively large.

2. Trade-off Between Queries and Soundness

Theorem 1.6: The authors derive a refined trade-off. By repeating the decoder $t$ times and discarding nonsmoothable samples, they achieve an error probability of $\rho^t$, where $\rho < 1$. This provides a better amplification of soundness than standard majority voting for LDCs.

3. Lower Bounds for RLDCs and RLCCs

By combining their transformation with existing lower bounds for LDCs (e.g., [JM25], [AGKM23]), they derive new lower bounds for RLDCs and Relaxed Locally Correctable Codes (RLCCs) without assuming linearity.
Corollary 1.7: For a $(q, \delta, 1, s)$-RLDC with $s \le 2^{-q/2}$, the codeword length $n$ must satisfy $k \le O(n^{1 - 2/q} \log n)$. This matches the best known lower bounds for standard LDCs, implying that "good" RLDCs cannot beat the LDC lower bounds.

4. Lower Bounds for PCPPs

Corollary 1.10: They establish a lower bound for a specific type of 3-query Probabilistically Checkable Proofs of Proximity (PCPPs). They show that for certain query distributions, achieving very small soundness error requires a proof length of at least $N^2 / \text{poly}(\log N)$, where $N$ is the circuit size.

4. Significance and Impact

• Unification of LDC and RLDC Theory: The paper demonstrates that the distinction between LDCs and RLDCs is not about the existence of efficient codes, but strictly about the soundness error. If an RLDC is "too good" (i.e., has very low soundness error), it collapses into a standard LDC.
• Resolution of Open Questions: It answers the question of whether nonlinear RLDCs can bypass LDC lower bounds. The answer is no, provided the soundness error is sufficiently small. The superior parameters of known RLDCs (like $n = k^{1+O(1/q)}$) are achieved precisely because they tolerate a higher soundness error.
• Technological Advancement: The introduction of codeword-relative smoothness provides a powerful new tool for analyzing nonlinear codes, which may be applicable to other problems in property testing and coding theory.
• Implications for PCPPs: The results tighten the understanding of the limitations of PCPPs, showing that certain "relaxed" proof systems cannot achieve both short length and extremely low soundness error simultaneously.

In summary, the paper establishes that relaxation in local decoding is only useful if one is willing to accept a non-negligible probability of outputting a wrong symbol. If the soundness error is pushed below a specific threshold, the code must inherently possess the structure of a standard LDC, inheriting its known lower bounds.