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.

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

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.