Universal Locally Testable Codes
Universal Locally Testable Codes
复制标题
通用本地可测试代码
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Tom Gur
中科院分区：
文献类型：
--
作者：
Oded Goldreich;Tom Gur
我们开始了对“通用局部可测试码”(Universal-LTCs)的研究。这些代码允许在许多可能的子代码中对成员资格进行本地测试，从而允许测试编码消息的属性。更确切地说，对于函数族F={FI：{0，1}k→{0，1}}I→[M]，泛LTCC：{0，1}k∈{0，1}n是这样的码：对于每个I∈[M]，子码{C(X)：FI(X)=1}是局部可测的。我们证明了对任何M函数族F都有一个长度为(M·S)的“正则”O(1)-局部泛LTC，使得每个f∈F都可以用一个大小为S的回路来计算，并建立了n=M1/O(K)形式的下界，这个下界可以加强到对任意F n=MΩ(1)，使得每个f，f‘∈F在其定义域的一个常分数上不一致.
We initiate a study of “universal locally testable codes" (universal-LTCs). These codes admit local tests for membership in numerous possible subcodes, allowing for testing properties of the encoded message. More precisely, a universal-LTCC : {0,1}k→{0,1}n for a family of functions F = { fi : {0,1}k→{0,1} } i∈[M] is a code such that for every i ∈ [M] the subcode {C(x) : fi(x) = 1} is locally testable. We show a “canonical" O(1)-local universal-LTC of length Õ(M · s) for any family F of M functions such that every f ∈ F can be computed by a circuit of size s, and establish a lower bound of the form n = M1/O(k), which can be strengthened to n = MΩ(1) for any F such that every f , f ′ ∈ F disagree on a constant fraction of their domain.