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.