Better lower bounds for locally decodable codes
Better lower bounds for locally decodable codes
复制标题
本地可解码代码的更好下限
DOI：
10.1109/ccc.2002.1004354
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Satyanarayana V. Lokam
中科院分区：
文献类型：
--
作者：
A. Deshpande;Rahul Jain;T. Kavitha;J. Radhakrishnan;Satyanarayana V. Lokam
如果随机算法可以通过仅读取可能损坏的消息编码的少数符号来恢复任何单个消息，则认为错误纠正校正代码是可以在本地解释的。 Katz和Trevisan（2000）表明，任何此类代码c：{0，1}/spl rarr//spl sigma //使用解码算法的SUP M/SUP M/，该算法最多使Q探针必须满足M =/Spl Omega/（（（（（（（（（（（（（（（（（（（ n/log |/spl sigma/|）/sup q/（q-1）/）。他们假设解码算法是非自适应的，并且打开了证明适应性解码器相似界限的问题。我们通过两种方式提高了Katz和Trevisan（2000）的结果。首先，我们给他们的结果提供了更直接的证明。其次，这是我们的主要结果，我们证明M =/Spl Omega/（（（n/log |/spl sigma/|）/sup q/（q-1）/）即使解码算法是适应性的，也是如此。我们证明的重要组成部分是一种随机方法，用于平滑自适应解码算法。我们采用的主要技术工具是第二刻方法。
An error-correcting code is said to be locally decodable if a randomized algorithm can recover any single bit of a message by reading only a small number of symbols of a possibly corrupted encoding of the message. Katz and Trevisan (2000) showed that any such code C: {0, 1} /spl rarr/ /spl Sigma//sup m/ with a decoding algorithm that makes at most q probes must satisfy m = /spl Omega/((n/log |/spl Sigma/|)/sup q/(q-1)/). They assumed that the decoding algorithm is non-adaptive, and left open the question of proving similar bounds for adaptive decoders. We improve the results of Katz and Trevisan (2000) in two ways. First, we give a more direct proof of their result. Second, and this is our main result, we prove that m = /spl Omega/((n/log|/spl Sigma/|)/sup q/(q-1)/) even if the decoding algorithm is adaptive. An important ingredient of our proof is a randomized method for smoothing an adaptive decoding algorithm. The main technical tool we employ is the Second Moment Method.