BLR 线性测试 | Codeboy's Blog

形式陈述

被测试的性质

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

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

对所有 $x$ 成立，其中 $\langle a,x\rangle=\sum_i a_ix_i$ ，在 $\mathbb F_2$ 中计算。在性质测试口径下，每个对象的显式表示是长度 $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>0$ ，全部漏检概率至多 $(1-\delta)^k\le e^{-k\delta}$ 。对 $0<\eta<1$ ，取整数 $k\ge\lceil\delta^{-1}\ln(1/\eta)\rceil$ 即可，总查询至多为 $3k$ 。

按 $n$ 位向量表示地址时，每轮生成 $2n$ 个新独立随机位，并以 $O(n)$ 位操作计算 $x+y$ ，复用 $O(n)$ 位向量工作空间；执行至多 $k$ 轮需 $O(kn)$ 此类位操作和随机位，提前拒绝会减少实际用量。循环计数器另需 $O(\log(k+1))$ 位，函数 oracle 的求值成本另计。

完备性

若 $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$ 。对于仿射函数 $f(x)=\langle a,x\rangle+b$ ，左右两边的差恰为 $b$ ；若 $b=1$ ，每个随机对都会使测试拒绝。要测试仿射性，可先用 $f(x)+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$ ，测试拒绝。

在这张腐化后的四点表上，恰有六个有序对会失败： $x,y$ 是两个不同的非零向量。故单次拒绝概率为 $6/16=3/8$ ，而到最近线性函数的距离是 $1/4$ 。另一些随机三元组可能通过，所以“一次发现”不是 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)]$ 。令 $z_i=(-1)^{x_i}$ ，则 $\chi_a(x)=\prod_{i:a_i=1}z_i$ ，与符号 cube 上的字符一一对应。利用Fourier–Walsh 字符正交性展开三重相关，得到

\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$ 。

推论与应用

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

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

本页的三重相关使用字符基识别近线性结构。完整 Fourier–Walsh 展开进一步把任意布尔函数的方差、影响与各层质量统一表示；KM 算法则主动查询共享后缀的输入对，递归寻找多个显著系数。后者输出的是可学习频谱结构，目标并非三查询的线性性质检验。

参考资料

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 恒等式 ​

反向链接

形式陈述

被测试的性质

三查询算法

完备性

一个具体拒绝轨迹

Fourier soundness 恒等式