Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
Three-Query Locally Decodable Codes with Higher Correctness Require Exponential Length
复制标题
正确性较高的三查询本地可解码代码需要指数长度
DOI：
10.1145/2077336.2077338
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Andrew Mills
中科院分区：
文献类型：
--
作者：
A. Gál;Andrew Mills
局部可解码码是具有额外属性的纠错码，为了检索单个输入位置的值，读取码字的少量位置就足够了。我们将获得正确值的概率称为解码算法的正确性。
Yekhanin [2007]的一个突破性结果表明，3-查询线性局部可解码码可能具有亚指数长度。Yekhanin的构造以及随后的三个查询构造只能达到一定的正确性限制，对于非二进制代码是1 − 3Δ，其中允许攻击者破坏代码的Δ部分。Woodruff [2008]在一个构造中实现了亚指数长度3-查询二进制码的最大正确率，它低于1 − 3Δ。
我们表明，实现稍大的正确性（作为Δ的函数）需要指数码字长度为3查询代码。以前，有没有大于二次下界已知的本地解码代码与超过2个查询，即使在3查询线性码的情况下。我们的下界保持在任意有限域上的线性码和二元非线性码。考虑到大量的查询，我们得到了下界的q-查询代码的q > 3，在一定的假设下的解码算法，通常用于以前的建设。我们还证明了这些解码算法所能达到的最大正确性的界限，无论代码的长度。我们的研究结果解释了在以前的建设中使用这样的解码算法的正确性的局限性。此外，我们的研究结果意味着权衡的纠错数据结构的参数。
Locally decodable codes are error-correcting codes with the extra property that, in order to retrieve the value of a single input position, it is sufficient to read a small number of positions of the codeword. We refer to the probability of getting the correct value as the correctness of the decoding algorithm.
A breakthrough result by Yekhanin [2007] showed that 3-query linear locally decodable codes may have subexponential length. The construction of Yekhanin, and the three query constructions that followed, achieve correctness only up to a certain limit which is 1 − 3Δ for nonbinary codes, where an adversary is allowed to corrupt up to Δ fraction of the codeword. The largest correctness for a subexponential length 3-query binary code is achieved in a construction by Woodruff [2008], and it is below 1 − 3Δ.
We show that achieving slightly larger correctness (as a function of Δ) requires exponential codeword length for 3-query codes. Previously, there were no larger than quadratic lower bounds known for locally decodable codes with more than 2 queries, even in the case of 3-query linear codes. Our lower bounds hold for linear codes over arbitrary finite fields and for binary nonlinear codes. Considering larger number of queries, we obtain lower bounds for q-query codes for q > 3, under certain assumptions on the decoding algorithm that have been commonly used in previous constructions. We also prove bounds on the largest correctness achievable by these decoding algorithms, regardless of the length of the code. Our results explain the limitations on correctness in previous constructions using such decoding algorithms. In addition, our results imply trade-offs on the parameters of error-correcting data structures.