局部可测试码

局部可测试性要求码的全局成员资格留下大量短小而一致的痕迹。码字必须通过每个被抽到的局部检查；一个离整个码很远的接收词，则不能只在极少数角落隐藏所有矛盾，否则少量查询永远看不见它与全局结构的距离。

真正困难的是局部到全局的反推。设计几条低重量校验很容易，证明“多数校验通过”迫使接收词靠近同一个码字”才构成 soundness。若不同局部视图各自接近不同候选，局部一致并不会自动拼成全局编码。

Repetition code 的完整 tester ​

二元 repetition code

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

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

随机两位置不同的概率为

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

线性码与局部约束 ​

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

每个码字通过所有 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 证明。

与局部恢复的边界 ​

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

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

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

LTC 把编码、性质测试与 PCP 中的局部验证连接起来：短随机检查若同时具有完备性、soundness 和可组合的 robustness，就能让验证者不读取完整证明仍检测全局不一致。具体转换还取决于 rate、距离、alphabet 和局部视图长度，不能只比较查询数。

分析一个候选 LTC 时，可以沿两条链分别检查：代数链说明合法码字为何总通过，组合链说明远词为何违反足够多约束。前者通常是一行恒等式，后者才决定 tester 是否真正看得到全局距离。