期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2010
卷号：2010
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Locally testable codes are error-correcting codes for which membership of a given word in the code can be tested probabilistically by examining it in very few locations.
A linear code C\Fn2 is called sparse if dim(C)=O(log(n)).
We say that a code C\Fn2 is -biased if all nonzero codewords of C have relative weight in the range (21−21+), where may be a function of n.
Kaufman and Sudan \cite{KS07} proved that all sparse linear codes with relative distance 21−n−(1) are locally testable. Moreover, they showed that all sparse n−(1)-biased linear codes are locally decodable. In particular sparse random codes are locally testable and are locally decodable with probability 1−o(1).
Kopparty and Saraf \cite{KopS09} conjectured that all sparse linear codes (even with a bad distance) are locally testable.
In this paper we refute this conjecture by showing that for every d(n) ranging from (1) to (n) there exists a family of codes \setC(n)\Fn2n\ints with linear distance and dim(C(n))=(d(n)) which are not locally testable (decodable). Furthermore, we show that there exists a family of codes \setC(n)\Fn2n\ints with bias n−o(1) and dim(C(n))=log(n) which are not locally testable (decodable). This also shows that the results of Kaufman and Sudan \cite{KS07} were surprisingly tight.
Changes to previous version:
The tight upper bound on the redundancy of the tester for LTC was added.
