ECCC-Report TR23-064https://eccc.weizmann.ac.il/report/2023/064Comments and Revisions published for TR23-064en-usWed, 03 May 2023 17:52:01 +0300
Paper TR23-064
| On the Lower Bound on the Length of Relaxed Locally Decodable Codes |
Oded Goldreich
https://eccc.weizmann.ac.il/report/2023/064We 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.
Wed, 03 May 2023 17:52:01 +0300https://eccc.weizmann.ac.il/report/2023/064