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.
For uncorrupted codewords, and for every bit, the decoder must decode the bit correctly with high probability.
However, for a noisy codeword, a relaxed local decoder is allowed to output a ``rejection'' symbol, indicating that the decoding failed.
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 local decoders to non-adaptive, one-sided error ones.
That is, the reduction produces a relaxed local 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 essentially maintains the query complexity, requiring at most one additional query.
For any input, the decoder's error probability increases at most two-fold.
Furthermore, assuming the underlying code is in systematic form, where the original message is embedded as the first bits of its encoding, the reduction also conserves both the code itself and its rate and distance properties
We base the reduction on our new notion of *additive* promise problems.
A promise problem is additive if the sum of any two YES-instances is a YES-instance and the sum of any NO-instance and a YES-instance is a NO-instance.
This novel framework captures both linear RLDCs and property testing (of linear properties), despite their significant differences.
We prove that in general, algorithms for *any* additive promise problem do not gain power from adaptivity or two-sided error, and obtain the result for RLDCs as a special case.
The result also holds for relaxed locally *correctable* codes (RLCCs), where a *codeword* bit should be recovered.
As an application, we improve the best known lower bound for linear adaptive RLDCs.
Specifically, we prove that such codes require block length of $n \geq k ^ {1+\Omega(1/q^2)}$, where $k$ denotes the message length and $q$ denotes the number of queries.
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.
For uncorrupted codewords, and for every bit, the decoder must decode the bit correctly with high probability.
However, for a noisy message, a relaxed local decoder is allowed to output a ``rejection'' symbol, indicating that the decoding failed.
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 local decoders to non-adaptive, one-sided error ones.
That is, the reduction produces a relaxed local 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.
We base the reduction on our new notion of *additive* promise problems.
A promise problem is additive if the sum of any two YES-instances is a YES-instance and the sum of any NO-instance and a YES-instance is a NO-instance.
This novel framework captures both linear RLDCs and property testing (of linear properties), despite their significant differences.
We prove that in general, algorithms for *any* additive promise problem do not gain power from adaptivity or two-sided error, and obtain the result for RLDCs as a special case.
The result also holds for relaxed locally *correctable* codes (RLCCs), where a *codeword* bit should be recovered.
As an application, we improve the best known lower bound for linear adaptive RLDCs.
Specifically, we prove that such codes require block length of $n \geq k ^ {1+\Omega(1/q^2)}$, where $k$ denotes the message length and $q$ denotes the number of queries.
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.
