局部可测试码

代码作为性质 ​

设编码映射

$$\mathrm{Enc}:{\mathrm{\Sigma }}^k\to {\mathrm{\Sigma }}^N$$

的像为码 $C\subseteq {\mathrm{\Sigma }}^N$。把接收词 $w\in {\mathrm{\Sigma }}^N$ 视为 oracle，对码的距离取

$$\mathrm{dist}(w,C)=\underset{c\in C}{min}\frac{d_H(w,c)}{N}.$$

若存在查询数 $q(\epsilon )$ 远小于 $N$ 的 tester，满足 $w\in C$ 时接受、$\mathrm{dist}(w,C)\ge \epsilon$ 时以常数概率拒绝，就称该码局部可测试。它是性质测试公理库性质测试模型Property testing model · Property testing通过少量 oracle 查询区分完全满足性质的对象与到该性质至少相距 ε 的对象，并允许 gap 内行为任意。在编码集合上的专门化。

常见强定义要求一次局部试验的拒绝概率至少

$$\rho (\mathrm{dist}(w,C)),$$

其中 soundness function $\rho$ 随全局距离增长。重复局部试验可放大常数可靠性，但查询数随重复次数增加。

参数不能只剩 q ​

LTC 还要同时报告 block length $N$、message length $k$、rate $k/N$、码的相对距离、字母表大小 $|\mathrm{\Sigma }|$、查询数 $q$ 和 soundness。常数查询若以指数长度或巨大 alphabet 为代价，和高 rate 二进制 LTC 是不同结果。

Tester 的随机性通常只选少量坐标和局部约束；本地计算免费。若一次查询返回整个大 alphabet 符号，答案 bit 数为 ${\log }_2|\mathrm{\Sigma }|$，不能在跨模型比较时忽略。

Repetition code 的完整 tester ​

二元 repetition code

$$C=\{0^N,1^N\}$$

编码一 bit，rate 为 $1/N$。一次局部试验独立均匀选择两个坐标 $I,J$，查询 $w_I,w_J$，相同则接受、不同则拒绝。

码字所有符号一致，因而 perfect completeness。令 $\alpha$ 为较少出现的 bit 比例，则

$$\mathrm{dist}(w,C)=\alpha \le \frac{1}{2}.$$

随机两位置不同的概率为

$$2\alpha (1-\alpha )\ge \alpha .$$

所以距离至少 $\epsilon$ 时，一次试验拒绝概率至少 $\epsilon$；重复 $O({\epsilon }^{-1}\log \left(1/\delta \right))$ 次可把漏检率降到 $\delta$。这是合法 LTC，却用极低 rate 换来简单局部约束，不能作为高效编码的全部故事。

线性码与局部约束 ​

对线性码公理库线性码Linear code有限域向量空间中的线性子空间作为码字集合的信道码。，局部测试常随机选择一个低重量 dual codeword $h$，查询其支持并检查

$$⟨h,w⟩=0.$$

每个码字通过所有 parity checks，给出完备性。Soundness 的困难是证明任意远离 $C$ 的词会违反足够多可抽到的局部 checks；存在一个稀疏校验矩阵并不自动保证这一点。

Hadamard code 的码字是线性函数真值表，BLR 测试公理库BLR 线性测试BLR linearity test · Blum-Luby-Rubinfeld linearity test以三个函数值检查 f(x)+f(y)=f(x+y)，并用 Fourier 一致性证明高通过率函数接近某个线性函数。用三个查询检查 $w(x)+w(y)=w(x+y)$。其 Fourier soundness 正是“高比例局部等式成立蕴含接近同一个全局码字”的 LTC 证明。

Robustness ​

普通 tester 只输出 pass/fail。Robust tester 对一次随机局部视图，计算它到最近可接受局部配置的相对距离，并要求该局部距离的期望控制全局 $\mathrm{dist}(w,C)$。

Robustness 比“至少有一条局部约束失败”更适合组合与 proof composition，因为它量化失败幅度。二者的 soundness 参数可以转换但不完全相同，引用时应说明测量的是拒绝概率还是局部距离。

与局部恢复的边界 ​

LTC tester 只决定 $w$ 是否像某个码字，不知道发送消息，也不输出最近码字符号。局部译码与纠错公理库局部译码与局部纠错Locally decodable code · Locally correctable code · Local decoding在接收词接近某个码字时，以少量坐标查询恢复指定消息符号或指定码字符号。给定目标坐标并尝试恢复数据，是另一项保证。

一个码可以局部可测试却没有同样查询量的局部译码器，也可能拥有局部纠错结构却缺少强测试 soundness。测试、译码、纠错的 oracle 相同，输出目标和量词不同。

最后，far 表示到 所有 码字都远。发现接收词与某个候选消息编码不一致，只排除一份码字，不能据此拒绝整个码性质。

参考资料

• Oded Goldreich and Madhu Sudan, “Locally Testable Codes and PCPs of Almost-Linear Length,” Journal of the ACM 53(4), 2006, pp. 558–655.
• Eli Ben-Sasson and Madhu Sudan, “Robust Locally Testable Codes and Products of Codes,” Random Structures & Algorithms 28(4), 2006, pp. 387–402.
• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapter 13.