Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-019 | 9th February 2005 00:00

Tolerant Locally Testable Codes



An error-correcting code is said to be {\em locally testable} if it has an
efficient spot-checking procedure that can distinguish codewords
from strings that are far from every codeword, looking at very few
locations of the input in doing so. Locally testable codes (LTCs) have
generated a lot of interest over the years, in large part due to
their connection to Probabilistically checkable proofs (PCPs). The
ability to correct errors that occur during transmission is one of the big advantages of
using a code. Hence, from a coding-theoretic angle, local testing is
potentially more useful if in addition to accepting codewords, it
also accepts strings that are close to a codeword (in contrast,
local testers can have arbitrary behavior on such strings, which
potentially annuls the benefits of error-correction). This
would imply that when the tester accepts, one can follow-up the
testing with a (more expensive) decoding procedure to correct the
errors and recover the transmitted codeword, while if the tester
rejects, we can save the effort of running the more expensive
decoding algorithm.

In this work, we define such testers, which we call {\em tolerant testers}
following some recent work in property testing~\cite{PRR04}. We
revisit some recent constructions of LTCs and show how one can
make them locally testable in a tolerant sense. While we do
not optimize the parameters, the main message from our work is that
there are explicit tolerant LTCs with similar parameters to LTCs

ISSN 1433-8092 | Imprint