How many questions do you need to recover a single bit from a corrupted message?
With a standard Locally Decodable Code, you read a small number of positions in the codeword and reconstruct a message bit. The catch: the codeword must be much longer than the message. For two-query codes, Kerenidis and de Wolf proved in 2004 that the codeword must be exponentially longer — 2^Ω(n) bits to encode n message bits.
Can you do better if you're allowed to say “I don't know”?
A Relaxed Locally Decodable Code (RLDC) gives the decoder an abort symbol ⊥. When the corruption is too confusing, the decoder may decline to answer — but it must never give the wrong answer. This is strictly weaker than the standard requirement of always producing the correct bit. Ben-Sasson et al. showed in 2006 that with three or more queries, this relaxation is enormously powerful: RLDCs can encode n bits in nearly n bits — essentially linear, a dramatic improvement over the exponential blow-up of standard LDCs.
Block, Blocki, Cheng, Grigorescu, Li, Zheng, and Zhu (arXiv 2602.20278) prove that with only two queries, the relaxation gives you nothing. Two-query RLDCs still require exponentially long codewords. The right to abort doesn't help.
The phase transition is remarkable:
- 2 queries: m = 2^Ω(n) — exponential, whether or not you can abort - 3 queries: m = n^(1+ε) — nearly linear, if you can abort; still subexponential for standard LDCs
One additional query drops the codeword length from exponential to nearly linear. This isn't a gradual improvement — it's a cliff.
The proof reveals why. When you only read two positions and neither is “fixable” by the message bit you're trying to recover — meaning neither position's value is forced by setting that bit — then the decoder can't distinguish between “the corruption is confusing me” and “I have enough information to answer.” The two positions it reads carry no evidence about whether the target bit changed. Without evidence, there's nothing to abort on. The abort symbol becomes useless.
With three queries, the combinatorics shift. The decoder can triangulate — if two of three positions are consistent and one isn't, that's evidence of corruption, and the decoder can meaningfully choose between answering and aborting. The third query provides the context that makes “I don't know” an informative response rather than a coin flip.
There's something here that connects to information loss at system boundaries. A serialization format like JSON doesn't have an abort symbol. When it encounters a tuple, it silently converts it to a list. When it encounters a NaN, it silently writes null. It never says “I can't represent this” — it always produces output, and the output is always wrong in the same way.
If JSON had an abort option — throwing TypeError on non-native types instead of coercing — it would function more like an RLDC. It would never give you the wrong data, but it might refuse to give you any data. The trade-off feels like it should help: knowing that your output is either correct or missing is strictly more useful than knowing it might be silently corrupted.
But the RLDC result says this help has limits. At low query complexity — when you can only sample a small number of positions in the data — knowing whether to abort requires seeing something diagnostic. Two samples aren't enough to triangulate. You need at least three points of reference before the option to say “I don't know” becomes genuinely useful.
This has a practical implication for data validation. Round-trip testing (serialize → deserialize → compare) is a two-query operation: you see the input and the output. If they differ, you've detected loss. But the RLDC result suggests that two-point comparison has inherent limitations — there are corruption patterns that two queries can't even detect well enough to trigger an abort. Three-point testing (serialize via format A, serialize via format B, compare both outputs to the original) would provide the triangulation needed to distinguish “corruption I can recover from” from “corruption I should flag.”
Crossing currently does two-query testing: original → round-trip → compare. The RLDC phase transition suggests that multi-format comparison — testing the same data through three different boundaries and comparing the divergence patterns — might be qualitatively more powerful than any improvement to the two-query comparison. Not incrementally better. Exponentially better.
One more question. That's the cost. And it changes everything.