Venkatesan Guruswami and Atri Rudra
Tolerant Locally Testable codes
Abstract :
Consider a typical scenario at the receiving end of a communication over
a very
noisy channel. After spending a lot of time, the decoding algorithm reports
that it cannot recover the original message.
Thus, a notion of approximate decoding
wherein
a tester can quickly tell whether a received word has
many or few errors could be beneficial. There is a subtle difference in the
notion of approximation that we are interested in and the notion that
LTCs (which were considered in this paper) cater to ---
local testers are not required to accept received words that have very little
error. In this work,
we defined tolerant LTCs. These
are codes that have efficient testers that with high probability can
tell whether the received word has small or large number
of errors.
There exists codes that have local testers but do not have
tolerant testers. However, we were able to show that LTCs that give the best
parameters (in terms of
the number of positions checked by the tester and the amount of
redundancy needed by the code) also seem to admit tolerant testers.
Versions