Combinatorial construction of locally testable codes
Combinatorial construction of locally testable codes
复制标题
本地可测试代码的组合构造
DOI：
10.1145/1374376.1374419
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Or Meir
中科院分区：
文献类型：
--
作者：
Or Meir
如果存在通过仅读取串的恒定数目的符号来检查给定串是否是码字或者更确切地说是远离码的测试，则纠错码被称为本地可测试的。局部可测码(LTCs)最早是由Goldreich和苏丹(J.ACM53(4))系统地研究的，此后人们提出了几种局部可测码的构造方法。虽然Ben-Sasson和苏丹(STOEC 2005)和Dinur(J.ACM 54(3))最著名的LTC构造实现了非常有效的参数，但它严重依赖于代数工具和PCP机器。在这项工作中，我们提出了一种新的、可以说是更简单的LTC结构，它是纯粹的组合结构，不依赖于PCP机械，并且与最著名的结构的参数相匹配。然而，与后一种结构不同的是，我们的结构并不完全明确。
An error correcting code is said to be locally testable if there is a test that checks whether a given string is a codeword, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first systematically studied by Goldreich and Sudan (J. ACM 53(4)) and since then several Constructions of LTCs have been suggested. While the best known construction of LTCs by Ben-Sasson and Sudan (STOC 2005) and Dinur (J. ACM 54(3)) achieves very efficient parameters, it relies heavily on algebraic tools and on PCP machinery. In this work we present a new and arguably simpler construction of LTCs that is purely combinatorial, does not rely on PCP machinery and matches the parameters of the best known construction. However, unlike the latter construction, our construction is not entirely explicit.