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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

On the Relaxed LDC of BGHSV: A Survey that Corrects the Record

  • Oded Goldreich

摘要

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.