Robust Locally Testable Codes and Products of Codes
<|reference_start|>Robust Locally Testable Codes and Products of Codes: We continue the investigation of locally testable codes, i.e., error-correcting codes for whom membership of a given word in the code can be tested probabilistically by examining it in very few locations. We give two general results on local testability: First, motivated by the recently proposed notion of {\em robust} probabilistically checkable proofs, we introduce the notion of {\em robust} local testability of codes. We relate this notion to a product of codes introduced by Tanner, and show a very simple composition lemma for this notion. Next, we show that codes built by tensor products can be tested robustly and somewhat locally, by applying a variant of a test and proof technique introduced by Raz and Safra in the context of testing low-degree multivariate polynomials (which are a special case of tensor codes).   Combining these two results gives us a generic construction of codes of inverse polynomial rate, that are testable with poly-logarithmically many queries. We note these locally testable tensor codes can be obtained from {\em any} linear error correcting code with good distance. Previous results on local testability, albeit much stronger quantitatively, rely heavily on algebraic properties of the underlying codes.<|reference_end|>
@article{ben-sasson2004robust,
    title={Robust Locally Testable Codes and Products of Codes},
    author={Eli Ben-Sasson and Madhu Sudan},
    journal={arXiv preprint arXiv:cs/0408066},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0408066},
    primaryClass={cs.IT cs.CC math.IT}
}