🔢 mathematics

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes

This paper establishes the first exponential lower bound on the codeword length of 2-query relaxed locally decodable codes over the binary alphabet in the Hamming-error setting, thereby resolving a question posed by Gur and Lachish and revealing a phase-transition behavior in codeword length for constant-query complexity.

Original authors: Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu

Published 2026-03-03

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu

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 have a massive, secret library of books (your data). To protect these books from being damaged by fire, water, or mischievous gremlins (errors), you create a special, super-long version of each book called a Codeword. This version is so redundant that even if half the pages are torn out or scribbled over, you can still figure out what the original story was.

This is the job of Error-Correcting Codes.

The Problem: Reading the Library Too Slowly

Usually, to read just one specific sentence from your original book, you have to scan the entire super-long codeword. That's like reading a 1,000-page encyclopedia just to find out the capital of France. It's accurate, but it's slow.

Locally Decodable Codes (LDCs) are a magical invention. They allow you to find that one sentence by looking at only two random pages of the codeword. It's like having a magical index that lets you jump straight to the answer.

However, there's a catch. For these codes to work with just two pages, the codeword has to be astronomically huge (exponentially larger than the original book). If you want to store a 100-page book, the codeword might need to be longer than the number of atoms in the universe. This makes them useless for real-world storage.

The "Relaxed" Loophole

A few years ago, some clever mathematicians discovered a loophole. They created Relaxed Locally Decodable Codes (RLDCs).

Think of this as a "good enough" version of the magic index.

The Rule: If you ask for a sentence, the decoder looks at two pages.
The Loophole: If the pages are too messy, the decoder is allowed to say, "I give up, I can't read this" (marked as ⊥).
The Promise: As long as the decoder doesn't give up too often, and when it does give an answer, it's always correct, we call it a success.

The amazing thing about this "Relaxed" version was that researchers found they could make the codeword almost as short as the original book (linear size). It seemed like we had finally cracked the code: small storage, fast reading, and error protection.

The Big Discovery: The "Phase Transition"

The authors of this paper (Block, Blocki, et al.) asked a simple question: "Does this magic trick work if we only allow the decoder to look at exactly TWO pages?"

They suspected the answer was no, but proving it was incredibly hard.

Their result is a bit like finding a sudden cliff in a smooth road.

At 2 Queries: If you force the decoder to look at only 2 pages, the "Relaxed" code explodes. It suddenly requires an exponential amount of space (back to the "universe-sized" problem). The magic trick fails completely.
At 3+ Queries: If you allow the decoder to peek at just one more page (3 total), the code shrinks back down to a manageable size.

This is what they call a "Phase Transition." It's like water:

At 2 degrees (2 queries), it's a solid block of ice (huge, rigid, impossible to use).
At 3 degrees (3 queries), it instantly melts into a liquid (small, flexible, usable).

How Did They Prove It? (The Detective Analogy)

To prove this, the authors acted like detectives trying to expose a fraud.

The Setup: They imagined a "Relaxed" decoder that claims it can read a 2-page index.
The Trap: They noticed that for the decoder to be "perfect" (never wrong when the book is clean), certain pages in the codeword must be "locked" to specific bits of the original message.
- Analogy: Imagine the decoder says, "To know if the first letter is 'A', I must check Page 5 and Page 10." The authors proved that if Page 5 is "locked" to the first letter, then Page 5 must be a direct copy of that letter (or its opposite). It can't be a complex mix.
The Transformation: They realized that if the decoder only looks at 2 pages, and one of those pages is "locked" to the message, the decoder is essentially just looking at the message directly. But if both pages are locked, the decoder is just guessing.
The "Random Restriction" Trick: They used a mathematical trick where they "froze" most of the original book (fixed most letters to be 0 or 1). This forced the codeword to shrink. They showed that after shrinking, the "Relaxed" code behaved exactly like a standard, non-relaxed code.
The Conclusion: Since we already know standard 2-page codes must be huge, and their "Relaxed" code transforms into a standard code, the "Relaxed" code must also be huge.

Why Does This Matter?

This paper closes a major gap in our understanding of data storage and cryptography.

For Computer Scientists: It tells us exactly where the limits are. We can't cheat the system with "Relaxed" codes if we want to keep the query count at 2. We must increase the number of queries to 3 to get small, efficient codes.
For the Future: It highlights a fascinating "tipping point" in mathematics. A tiny change (adding just one more query) changes the entire nature of the problem from impossible to easy.

In a nutshell: You can't have your cake and eat it too. If you want to read a secret message by looking at only two pages, you have to pay a massive price in storage space. But if you are willing to look at just three pages, the price drops to almost nothing. The authors proved that this "magic switch" happens exactly between 2 and 3 queries.

1. Problem Statement

The paper addresses the fundamental trade-offs in Locally Decodable Codes (LDCs) and their relaxed variant, Relaxed Locally Decodable Codes (RLDCs).

LDCs: Error-correcting codes allowing the recovery of any single message bit by querying only a small number ( $q$ ) of bits from a corrupted codeword.
The Gap: For standard LDCs with constant query complexity $q$ , the best known constructions have super-polynomial codeword lengths ( $m = \text{poly}(n)$ or higher), while the best lower bounds for $q \ge 3$ are only polynomial. However, for $q=2$ , it is known that $m = 2^{\Theta(n)}$ (exponential).
RLDCs: Introduced by Ben-Sasson et al. (2006), RLDCs allow the decoder to output a "failure" symbol ( $\perp$ ) with some probability, provided it succeeds on a large fraction of message bits. Surprisingly, RLDCs admit almost linear codeword lengths ( $m = n^{1+o(1)}$ ) for constant $q$ , contrasting sharply with standard LDCs.
The Conjecture: Gur and Lachish (2021) conjectured that this "phase transition" from exponential to linear length might not hold for the specific case of 2 queries. They hypothesized that even for RLDCs, 2 queries might still require exponential length, similar to standard LDCs.

Goal: Prove or disprove whether 2-query RLDCs over the binary alphabet require exponential codeword length.

2. Methodology

The authors prove the conjecture by establishing a transformation from a weak 2-query RLDC to a standard 2-query LDC. Since standard 2-query LDCs are known to require exponential length (Kerenidis and de Wolf, 2004), this transformation implies the same lower bound for RLDCs.

The proof proceeds through several key technical steps:

A. Analysis of "Fixable" Bits

The authors analyze the structure of the decoder's query functions.

Perfect Completeness: The decoder must output the correct bit with probability 1 if the codeword is error-free.
Fixable Bits: They define a codeword bit $C(x)_j$ as "fixable" by a message bit $x_i$ if setting $x_i$ to 0 or 1 forces $C(x)_j$ to a constant value.
Truth Table Constraints: If a decoder's function $f$ has a " $\perp$ " entry in its truth table, perfect completeness forces the queried codeword bits to be "fixable" by the target message bit $x_i$ . If a bit is not fixable, the decoder cannot output $\perp$ ; it must output 0 or 1 deterministically based on the inputs.

B. Query Structure Classification

The authors classify the decoder's queries into two cases based on the set $S_i$ (indices of codeword bits fixable by $x_i$ ):

Case 1 (Inside $S_i$ ): Both queries fall within $S_i$ .
Case 2 (Outside $S_i$ ): Both queries fall outside $S_i$ .

Crucial Observation: A "mixed" case (one query inside $S_i$ , one outside) essentially never occurs for a valid 2-query decoder with perfect completeness. If one query is outside $S_i$ , the output becomes independent of that query, effectively reducing it to a single query inside $S_i$ .

C. Polarizing Conditional Success Probabilities

The core of the transformation involves manipulating the error distribution to force the decoder into a specific behavior:

Assumption: Assume the set $S_i$ is small ( $|S_i| \le \delta m/2$ ).
Modification: Introduce errors specifically in the $S_i$ portion of the codeword to force the decoder to output the wrong bit (or $\perp$ ) when it queries $S_i$ .
Result: This forces the decoder's success probability to rely entirely on queries falling outside $S_i$ (Case 2).
Transformation: Since the decoder never outputs $\perp$ in Case 2 (due to the fixability analysis), the decoder restricted to these queries becomes a standard LDC with success probability $1/2 + \epsilon$ .

D. Handling Large $S_i$ via Random Restrictions

The assumption that $|S_i|$ is small does not hold for all message bits in the original code. To resolve this, the authors use random restrictions:

They fix a random subset of message bits to constants (0 or 1).
Entropy Argument: If a codeword bit depends on many message bits (large $|T_j|$ ), fixing a random subset of message bits will likely force that codeword bit to a constant.
Elimination: By eliminating codeword bits that become constant, they construct a restricted code where, for a linear fraction of message bits, the set $S_i$ is small enough to apply the transformation.

E. Adaptive Decoders

The proof is extended to adaptive decoders (where the second query depends on the first answer). The authors show that the first query determines the structure. They prove that if the first query is outside $S_i$ , the second query becomes irrelevant (the output is determined by the first query alone), preserving the "Case 1 vs. Case 2" dichotomy.

3. Key Contributions

First Exponential Lower Bound for RLDCs: The paper provides the first exponential lower bound for RLDCs, specifically for the 2-query case.
Resolution of the Gur-Lachish Conjecture: It confirms the conjecture that 2-query RLDCs require exponential length, matching the bounds for standard LDCs.
Phase-Transition Phenomenon: The results establish a sharp "phase transition" in RLDCs:
- At $q=2$ : Codeword length is Exponential ( $2^{\Omega(n)}$ ).
- At $q \ge 3$ (specifically $q > 2$ ): Codeword length can be Almost Linear ( $n^{1+o(1)}$ ).
  This highlights a fundamental difference between 2-query and 3+ query regimes in relaxed coding.
Transformation Technique: The paper introduces a novel method to transform weak RLDCs into standard LDCs by analyzing "fixable" bits and using random restrictions to control the query structure.

4. Main Results

Theorem 1: Let $C: \{0, 1\}^n \to \{0, 1\}^m$ be a weak adaptive $(2, \delta, 1/2+\epsilon)$ -RLDC. Then the codeword length $m$ satisfies:
$m = 2^{\Omega_{\delta, \epsilon}(n)}$
This holds even for:

Weak RLDCs: Codes satisfying only perfect completeness and relaxed decoding (not the full "success rate" condition).
Adaptive Decoders: Decoders where the second query depends on the first.
Binary Alphabet: The result is specific to $\Sigma = \{0, 1\}$ .

5. Significance and Implications

Theoretical Limits: The work closes a significant gap in understanding the power of relaxation in local decoding. It shows that relaxation does not help reduce the codeword length for the minimal query complexity of 2.
PCP Constructions: Since RLDCs are used to construct Probabilistically Checkable Proofs (PCPs), this result clarifies the limits of such constructions. It suggests that the "almost linear" PCPs derived from RLDCs require at least 3 queries to achieve their efficiency.
Open Questions:
- Exact Threshold: What is the exact query complexity $q$ where the transition from exponential to polynomial/linear length occurs? (Current results suggest it is between 2 and 3, but the exact integer threshold for general cases remains open).
- Imperfect Completeness: Does the bound hold if the decoder does not have perfect completeness (i.e., allows errors even on error-free codewords)?
- Larger Alphabets: The proof relies on binary properties; extending this to larger alphabets is an open problem.
- Standard LDCs: Can these techniques (perfect completeness analysis, random restrictions) be adapted to improve lower bounds for standard LDCs with $q \ge 3$ ?

In summary, this paper demonstrates that the "magic" of relaxed decoding that allows for linear-size codes only kicks in once the query complexity exceeds 2, reinforcing the hardness of 2-query decoding even with relaxed constraints.