Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR23-064 | 3rd May 2023 17:51

On the Lower Bound on the Length of Relaxed Locally Decodable Codes


Authors: Oded Goldreich
Publication: 3rd May 2023 17:52
Downloads: 230


We revisit the known proof of the lower bound on the length of relaxed locally decodable codes, providing an arguably simpler exposition that yields a slightly better lower bound for the non-adaptive case and a weaker bound in the general case.

Recall that a locally decodable code is an error correcting code that allows for the recovery of any desired bit in the message based on a constant number of randomly selected bits in the possibly corrupted codeword.
The relaxed version requires correct recovery only in case of actual codewords, while requiring that for strings that are (only) close to the code, with high probability, the local decoder outputs either the correct value or a special failure symbol (but not a wrong value).

The lower bounds we prove are $n\geq k^{1+\Omega(1/q^2)}$ for the non-adaptive case and $n\geq k^{1+\Omega(1/q^3)}$ for the general case, where $k$ denotes the message length, $n$ denotes the length of the codewords, and $q$ denotes the (constant) number of queries.

ISSN 1433-8092 | Imprint