Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error

by Guy Goldberg

Oded's comments

My initial reaction to this work, which refers to (local) decoding, was that this result should be a natural extension of an analogous result of Ben-Sasson, Harsha and Raskhodnikova, which refers to (local) testing linear properties; but then I got reminded that I tried this idea in the past and failed. Furthermore, the failure was due to the fact that the past attempt as well as the current strategy do not work for (non-relaxed) LDCs. Indeed, the question of whether adaptivity and two-sided error help (non-relaxed) linear LDCs remains open.

The abstract asserts that the error bound is at most doubled, but this is actually overly timid and a bit misleading: The fact is that the error bound of the resulting algorithm is at most the sum of the error bounds of the original algorithm (on YES- and NO-instances); that is, the error bound on YES-instances is transferred to the NO-instances, whereas the distinguishability gap is preserved (and one should not expect any better).

I especially like the abstraction (i.e., the notion of additive promise problems) that is introduced and used in this work. I'd actually state linear relaxed LDC as a special case of it by directly using this notion (rather than using a transformation). Specifically, a linear relaxed LDC is a linear code $C:\{0,1\}^k\to\{0,1\}^n$ that gives rise to a collection of promise problems such that the $i$th problem (for $i\in[k]$) is to distinguish between pairs $(b,C(x))$ such that $x_i = b$ and pairs $(b,w)$ such that $w$ is close to $C(x)$ and $x_i = 1-b$.

The original abstract

Relaxed locally decodable codes (RLDCs) are error-correcting codes in which individual bits of the message can be recovered by querying only a few bits from a noisy codeword. Unlike standard (non-relaxed) decoders, a relaxed one is allowed to output a ``rejection'' symbol, indicating that the decoding failed. To prevent the decoder from always rejecting, we demand that if its input is a valid codeword, then for every bit, the decoder is correct with high probability.

We study the power of adaptivity and two-sided error for RLDCs. Our main result is that if the underlying code is linear, *adaptivity and two-sided error do not give any power to relaxed local decoding.* We construct a reduction from adaptive, two-sided error relaxed decoders to non-adaptive, one-sided error ones. That is, the reduction produces a relaxed decoder that never errs or rejects if its input is a valid codeword and makes queries based on its internal randomness (and the requested index to decode), independently of the input. The reduction does not change the query complexity (nor the underlying code), and for any input, the decoder's error probability increases at most two-fold.

The idea behind the reduction is our new notion of *additive* promise problem. A promise problem is additive if the sum of any two YES-instances is a YES-instance (i.e., the YES instances are a subspace) and the sum of any NO-instance and a YES-instance is a NO-instance (i.e., the NO-instances are a collection of cosets).

We prove that relaxed decoding, interpreted as a promise problem, satisfies this definition. We construct a reduction that applies to *any* additive promise problem, allowing us to obtain the result for RLDCs. Our result also holds for relaxed locally *correctable* codes (RLCCs), where a *codeword* bit should be recovered.

See ECCC TR23-067.


Back to list of Oded's choices.