Tolerant Locally Testable Codes
Tolerant Locally Testable Codes
复制标题
宽容的本地可测试代码
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
A. Rudra
中科院分区：
文献类型：
--
作者：
V. Guruswami;A. Rudra
一个纠错码被称为局部可测试的，如果它有一个有效的抽查程序，可以区分码字和远离每个码字的字符串，在这样做时只看输入的很少位置。本地可测试代码（LTC）多年来引起了人们的极大兴趣，这在很大程度上是由于它们与概率可检验证明（PCP）的联系。纠正传输过程中出现的错误的能力是使用代码的一大优势。因此，从编码理论的角度来看，如果除了接受码字之外，本地测试还接受接近码字的字符串，则本地测试可能更有用（相反，本地测试器可以在这些字符串上具有任意行为，这可能会取消纠错的好处）。这将意味着，当测试器接受时，可以用（更昂贵的）解码过程来跟进测试，以纠正错误并恢复所传输的码字，而如果测试器拒绝，则可以节省运行更昂贵的解码算法的努力。
在这项工作中，我们定义了这样的测试器，我们称之为容忍测试器，遵循最近在属性测试中的一些工作[13]。我们重新审视了一些最近的建设LTC，并展示了如何可以使他们在本地测试的宽容的意义。虽然我们没有优化的参数，从我们的工作的主要信息是，有明确的宽容的LTC与LTC类似的参数。
An error-correcting code is said to be 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 tolerant testers following some recent work in property testing [13]. 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.