Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-067 | 7th May 2023 20:50

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


Authors: Guy Goldberg
Publication: 7th May 2023 22:30
Downloads: 104


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.

ISSN 1433-8092 | Imprint