Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR04-046 | 4th June 2004 00:00

Robust Locally Testable Codes and Products of Codes


Authors: Eli Ben-Sasson, Madhu Sudan
Publication: 4th June 2004 16:12
Downloads: 3157


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 robust
probabilistically checkable proofs, we introduce the notion of
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 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.

ISSN 1433-8092 | Imprint