BLR 线性测试 | Codeboy's Blog

形式陈述

被测试的性质

令定义域为向量空间 $G=\mathbb F_2^n$ ，对象是 oracle function $f:G\to\mathbb F_2$ 。目标性质由全部线性函数组成：存在 $a\in\mathbb F_2^n$ ，使

f(x)=\langle a,x\rangle\pmod2

对所有 $x$ 成立。在性质测试口径下，每个对象的显式表示是长度 $2^n$ 的真值表，距离取不同函数值所占比例

\operatorname{dist}(f,g) =\Pr_{x\sim U(G)}[f(x)\ne g(x)].

这些线性真值表构成Hadamard 码。测试器通过查询函数 oracle 的位置，而不是输入向量 $a$ ；本地加法和随机采样在有限域上完成。

三查询算法

一次 BLR 试验独立均匀抽取 $x,y\in G$ ，查询

f(x),\qquad f(y),\qquad f(x+y),

并在且仅在

f(x)+f(y)=f(x+y)\pmod 2

时接受。三个查询地址在看到答案前已经确定，所以试验非自适应；若等式失败，当前三元组就是一个不可由线性函数产生的拒绝 witness。

重复 $k$ 次并在任一次失败时拒绝，仍保持 perfect completeness。若单次拒绝概率至少 $\delta$ ，全部漏检概率为 $(1-\delta)^k\le e^{-k\delta}$ ，达到失败率 $\eta$ 需要 $k=O(\delta^{-1}\log(1/\eta))$ ，总查询为 $3k$ 。

完备性

若 $f(x)=\langle a,x\rangle$ ，则对每个 $x,y$ 都有

f(x+y) =\langle a,x+y\rangle =\langle a,x\rangle+\langle a,y\rangle =f(x)+f(y)\pmod 2.

因此线性函数在每条随机轨迹上都接受，完备性为 $1$ 。测试不接受一般 affine function $f(x)=\langle a,x\rangle+b$ ；若 $b=1$ ，取 $x=y=0$ 就会违反加法式。要测试 affine 性需改变方程或先消去 $f(0)$ 。

直觉

线性函数把向量加法变成输出加法，所以一个随机三元组能给出可直接验证的局部证书。Soundness 的难点是证明大量局部等式若大多成立，就必须围绕同一个全局线性字符对齐；Fourier 三重相关与 Parseval 正是把局部通过率连接到这个共同字符的桥。

左侧三查询三角形以 f(x)=1、f(y)=1、f(x+y)=0 闭合为绿色等式，右侧把最后一个值改为 1 后形成红色违例 — BLR 线性测试的三查询闭合

例子与边界

一个具体拒绝轨迹

在 $\mathbb F_2^2$ 上，线性函数 $f(x_1,x_2)=x_1+x_2$ 的表为

f(00)=0,\quad f(01)=1,\quad f(10)=1,\quad f(11)=0.

取 $x=01,y=10$ ，有 $x+y=11$ ，等式检查为 $1+1=0$ ，通过。现在只把表中 $f(11)$ 腐化为 $1$ ；同一三元组变成 $1+1\ne1$ ，测试拒绝。

另一些随机三元组可能避开腐化点而通过，所以“一次发现”不是 soundness 的全部。需要证明如果表远离每个线性函数，失败三元组在所有随机对中占有可观比例。

Fourier soundness 恒等式

把函数编码为 $F(x)=(-1)^{f(x)}\in\{-1,+1\}$ 。BLR 等式通过当且仅当

F(x)F(y)F(x+y)=1.

若单次拒绝概率为 $\delta$ ，则

\mathbb E_{x,y}[F(x)F(y)F(x+y)]=1-2\delta.

对字符 $\chi_a(x)=(-1)^{\langle a,x\rangle}$ 定义 Fourier 系数 $\widehat F(a)=\mathbb E_x[F(x)\chi_a(x)]$ 。利用字符正交性展开三重相关，得到

\mathbb E_{x,y}[F(x)F(y)F(x+y)] =\sum_{a\in G}\widehat F(a)^3.

Parseval 恒等式给 $\sum_a\widehat F(a)^2=1$ 。令 $M=\max_a\widehat F(a)$ ，则每项 $\widehat F(a)^3\le M\widehat F(a)^2$ ，所以

1-2\delta \le M\sum_a\widehat F(a)^2=M.

因此存在 $a$ 使 $\widehat F(a)\ge1-2\delta$ 。而

\widehat F(a) =1-2\Pr_x[f(x)\ne\langle a,x\rangle],

故 $f$ 到某个线性函数的距离至多 $\delta$ 。取逆否得到 soundness：若 $f$ 与每个线性函数的距离至少 $\varepsilon$ ，单次 BLR 拒绝概率至少 $\varepsilon$ 。

推论与应用

证明链不能缩成口号

“大多数局部方程成立”只给出三重相关接近 $1$ ；真正的全局结论来自 Fourier 恒等式、Parseval 和大系数对应某个一致线性字符。跳过这段，会遗漏为何不同局部三元组必须围绕 同一个 $a$ 对齐。

测试依赖 $x,y$ 独立均匀。偏置采样会改变字符正交与拒绝率；复用相关随机对也不能直接使用独立放大。对一般有限域、非阿贝尔群或高次多项式，测试方程和 soundness 常数都需重新证明。

距离按完整真值表的均匀 Hamming 比例计算。若 oracle 只允许从未知分布抽 $x$ ，或只在某个 promise 子集上查询，BLR 的随机加法点可能不可访问，原 tester 不再合法。

参考资料

Manuel Blum, Michael Luby, and Ronitt Rubinfeld, “Self-Testing/Correcting with Applications to Numerical Problems,” Journal of Computer and System Sciences 47(3), 1993, pp. 549–595.
Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapter 2.
Madhu Sudan, “Invariance in Property Testing,” Property Testing, Springer, 2010, pp. 211–229.

形式陈述 ​

被测试的性质 ​

三查询算法 ​

完备性 ​

一个具体拒绝轨迹 ​

Fourier soundness 恒等式 ​

证明链不能缩成口号 ​