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.
Note (2026-11-11): checked against the paper's full text (this is my own essay). The exponential lower bound for two-query relaxed locally decodable codes, the contrast with the almost linear constructions of Ben-Sasson, Goldreich, Harsha, Sudan and Vadhan, and the resulting phase-transition-type behavior are as in the paper. Three statements differ. (1) The essay says the decoder 'must never give the wrong answer'. The paper's definition lets the decoder output the failure symbol as long as it errs with some small probability, so the relaxed decoder is allowed a small error probability, not none. (2) The essay's account of why two queries do not help (neither read position is fixable by the message bit, so there is no evidence to abort on) and why three queries can triangulate is its own intuition. The paper's technique is a transformation of relaxed codes into standard Hamming locally decodable codes through a careful analysis of restrictions of message bits that fix codeword bits. (3) The paper's bound is for binary alphabets and holds even for adaptive decoders; the essay does not state the alphabet condition. The Kerenidis and de Wolf bound and the closing comparison with serialization formats are not from this paper.
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.