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

#### Webpage for a paper by Oded Goldreich

#### Abstract

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.

#### Material available on-line

- First version posted:
May 2023.
- Revisions: none yet.

Back to
either Oded Goldreich's homepage
or general list of papers.