局部可测试码 | Codeboy's Blog

形式陈述

代码作为性质

取至少含两个符号的有限字母表 $\Sigma$ 与整数 $1\le k\le N$ ，设单射编码映射

\operatorname{Enc}:\Sigma^k\to\Sigma^N

的像为组合块码 $C\subseteq\Sigma^N$ ，不要求它线性，也不预设随机信道。把接收词 $w\in\Sigma^N$ 视为 oracle，对码的距离取

\operatorname{dist}(w,C) =\min_{c\in C}\frac{d_H(w,c)}N.

本页采用非自适应、单侧错误的性质测试口径。给定 $0<\varepsilon\le1$ ，一个 $q$ 查询 tester 在每个接收词上都满足硬上限 $q$ ，并要求

w\in C\Longrightarrow\Pr[\mathrm{accept}]=1, \qquad \operatorname{dist}(w,C)\ge\varepsilon \Longrightarrow\Pr[\mathrm{reject}]\ge2/3.

中间距离不作输出保证。局部可测试性是码族的渐近要求：本文取相对最小距离有正常数下界的码族，并要求对每个固定 $\varepsilon>0$ ，存在不随块长 $N$ 增长的查询预算 $q(\varepsilon)$ 。若研究随 $N$ 增长的查询预算或下降的相对距离，应把这组不同参数明确写出；单个有限码“查询比全读少一些”本身不是这样的码族保证。[1]

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

\rho\bigl(\operatorname{dist}(w,C)\bigr),

其中 $\rho:[0,1]\to[0,1]$ 是非减 soundness function， $\rho(0)=0$ ，并在所关心的正距离范围提供正下界。重复局部试验可放大常数可靠性，但查询数随重复次数增加。

完整参数

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

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

Robustness

对一次非自适应、固定 $q\ge1$ 的局部试验，固定随机选择 $r$ 后，查询位置和接受谓词都已确定。令 $w|_r\in\Sigma^q$ 是回答向量， $A_r\subseteq\Sigma^q$ 是该谓词的非空接受集，并定义

\Delta_r(w)=\frac1q\min_{a\in A_r}d_H(w|_r,a).

Robustness 要求 $E_r\Delta_r(w)$ 下界某个关于全局 $\operatorname{dist}(w,C)$ 的函数。这里明确固定了随机选择对应的局部问题，不能对自适应路径无声套用同一视图定义。

局部通过时 $\Delta_r=0$ ；拒绝时 $1/q\le\Delta_r\le1$ 。因此

\frac1q\Pr[\mathrm{reject}] \le E_r\Delta_r(w) \le\Pr[\mathrm{reject}].

局部距离的下界直接给拒绝概率下界，反向转换可能损失 $q$ 倍。Robustness 为组合提供的是失败幅度，而不仅是某条约束失败；引用其 soundness 时须保留这个参数差别。

直觉

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

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

例子与边界

Repetition code 的完整 tester

二元 repetition code

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

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

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

\operatorname{dist}(w,C)=\alpha\le\frac12.

随机两位置不同的概率为

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

所以距离至少 $\varepsilon$ 时，一次试验拒绝概率至少 $\varepsilon$ ；对 $0<\delta<1$ ，用独立重复、任一次拒绝即拒绝，重复 $\lceil\varepsilon^{-1}\ln(1/\delta)\rceil$ 次可把漏检率降到 $\delta$ 。这是合法 LTC，却用极低 rate 换来简单局部约束，不能作为高效编码的全部故事。

线性码与局部约束

对线性码，局部测试常随机选择一个低重量 dual codeword $h$ ，查询其支持并检查

\langle h,w\rangle=0.

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

Hadamard code 的码字是线性函数真值表，BLR 测试用三个查询检查 $w(x)+w(y)=w(x+y)$ 。其 Fourier soundness 正是“高比例局部等式成立蕴含接近同一个全局码字”的 LTC 证明。

与局部恢复的边界

LTC tester 只决定 $w$ 是否像某个码字，不知道发送消息，也不输出最近码字符号。局部译码与纠错给定目标坐标并尝试恢复数据，是另一项保证。

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

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

推论与应用

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

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

参考资料

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.
[1] Oded Goldreich, Lecture Notes on Locally Testable Codes and Proofs，§2.1 Definitions 1–3 与 §2.3 的性质测试表述：单码参数、码族、相对距离与常数查询须分别规定；对应教材 Introduction to Property Testing, 2017, Chapter 13。

形式陈述 ​

代码作为性质 ​

完整参数 ​

Robustness ​

Repetition code 的完整 tester ​

线性码与局部约束 ​

与局部恢复的边界 ​

反向链接