期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2011
卷号：2011
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Locally decodable codes
are error correcting codes with the extra property that, in order
to retrieve the correct value of just one position of the input with
high probability, it is
sufficient to read a small number of
positions of the corresponding,
possibly corrupted codeword.
A breakthrough result by Yekhanin 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, 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 q3, 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 tradeoffs on the
parameters of error correcting data structures.
