Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-078 | 28th April 2024 19:29

On the relaxed LDC of BGHSV: A survey that corrects the record

RSS-Feed




Revision #1
Authors: Oded Goldreich
Accepted on: 28th April 2024 19:29
Downloads: 29
Keywords: 


Abstract:

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

We survey the relaxed LDC presented by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (in 2004).
For every constant $\alpha>0$, their code has block-length $n=k^{1+\alpha}$, whereas their decoder makes $O(1/\alpha)$ queries.
Unfortunately, their paper claims a $O(1/\alpha^2)$-query decoder,but the inferior complexity bound is merely due to a trivial oversight. This survey was triggered by a wish to correct the historical record.



Changes to previous version:

Correction for Section 4 retarding the issue of computing the code $C_\ell$.


Paper:

TR24-078 | 19th April 2024 15:29

On the relaxed LDC of BGHSV: A survey that corrects the record





TR24-078
Authors: Oded Goldreich
Publication: 19th April 2024 15:29
Downloads: 147
Keywords: 


Abstract:

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

We survey the relaxed LDC presented by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (in 2004).
For every constant $\alpha>0$, their code has block-length $n=k^{1+\alpha}$, whereas their decoder makes $O(1/\alpha)$ queries.
Unfortunately, their paper claims a $O(1/\alpha^2)$-query decoder,but the inferior complexity bound is merely due to a trivial oversight. This survey was triggered by a wish to correct the historical record.



ISSN 1433-8092 | Imprint