性质测试下界方法

下界必须固定完整模型 ​

一个性质测试下界至少同时固定：对象表示和 oracle、距离与 far 阈值、查询是否自适应、错误是单侧还是双侧，以及查询数按最坏还是期望计。改变任一项都会改变 tester 能观察的 transcript。

目标通常是证明：每个查询少于 $q$ 的 tester，都存在性质成员 $x\in \mathcal{P}$ 或 $\epsilon$-far 对象 $y$，使其错误超过允许常数。直接逐算法挑坏对象很难处理随机 tester；困难分布把问题转成确定性决策树的平均错误。

Hard distributions 与 Yao ​

构造 yes 分布 $\mathcal{Y}$，支持集完全落在 $\mathcal{P}$，以及 no 分布 $\mathcal{N}$，支持集完全由 $\epsilon$-far 对象组成。令混合先验先均匀选 yes/no，再从相应分布抽对象。

若能证明每个 $q$-query 确定性 tester 在该混合分布下错误大于 $1/3$，Yao 原理公理库Yao 极小极大原理Yao minimax principle · Yao principle · Yao's principle在有限输入与固定资源预算下，把最坏输入随机算法的最小损失等同于最难输入分布上的确定性最小平均损失。就排除 worst-case error 至多 $1/3$ 的随机 tester。此时确定性策略是查询决策树，成本是树深，而不是借用通信协议及其 bit 成本；两种下界共享同一个有限矩阵博弈，但模型参数必须各自固定。

两份分布必须在 promise 两侧。若 $\mathcal{N}$ 只是“通常很远”，少量 close 对象会让平均错误下界无法推出标准 tester 的 soundness；应条件化或证明其质量损失进入常数。

Transcript 的二点检验 ​

固定确定性 tester 后，对象随机性诱导两个 transcript 分布 $P_T$ 与 $Q_T$。在 equal prior 下，任何根据 transcript 判断 yes/no 的规则，最优成功率为

$$\frac{1+\mathrm{TV}(P_T,Q_T)}{2}.$$

因此若 $\mathrm{TV}(P_T,Q_T)<1/3$，错误必大于 $1/3$。这把性质测试下界变成二点检验下界公理库两点检验下界Le Cam's two-point method · two-point lower bound把两个目标相隔但观测分布接近的参数点化为二元检验，从而证明估计下界。：证明少量 oracle 回答在两种对象生成机制下统计上接近。

可以直接界 KL、Hellinger 或 χ² 散度再转成 total variation，也可以构造 coupling，使 yes/no 两次执行的 transcript 以概率至少 $1-\gamma$ 完全相同；后者立即给 $\mathrm{TV}\le \gamma$。

全零性质的 Ω(1/ε) 下界 ​

令 ${\mathcal{P}}_n=\{0^n\}$，使用 bit-query 和 normalized Hamming 距离。Yes 分布固定输出 $0^n$。No 分布均匀选择大小

$$m=\lceil \epsilon n\rceil$$

的坐标集合 $S$，并在 $S$ 上置 $1$、其余置 $0$；每个 no 对象都至少 $\epsilon$-far。

固定任意确定性自适应 tester。沿全零回答路径，它会依次选择至多 $q$ 个确定坐标，组成集合 $Q$。在 no 分布下，只要 $S\cap Q=\varnothing$，全部回答也为零，算法沿完全相同路径看到同一 transcript。由 union bound，

$$\text{Pr}[S\cap Q\ne \varnothing ]\le \frac{qm}{n}.$$

当 $\epsilon n\ge 1$ 时 $m/n\le 2\epsilon$。若 $q\le 1/(12\epsilon )$，命中概率至多 $1/6$，所以 no 对象以至少 $5/6$ 概率产生全零 transcript。

若 tester 在该 transcript 上接受，混合先验下来自 no 侧的错误至少 $(1/2)(5/6)=5/12$；若拒绝，yes 侧错误为 $1/2$。任一选择都超过 $1/3$。Yao 因而给出随机查询下界

$$q=\mathrm{\Omega }(1/\epsilon ),$$

与随机抽坐标的 $O(1/\epsilon )$ 上界匹配。证明允许 tester 自适应：在首次看到 $1$ 前，它的查询始终与全零路径一致，真正关键的是隐藏集合是否击中这条路径。

局部视图耦合 ​

图、函数和分布对象的 lower bound 常把 $\mathcal{Y},\mathcal{N}$ 耦合，使任何 $q$ 个局部查询看到同样的邻域、函数值或样本碰撞模式。自适应情况下，coupling 必须在线回答：每次根据共同历史同时延伸两边对象，并保持尚未暴露部分仍可补全为各自合法分布。

只证明每个固定查询集合边缘分布接近，不一定控制自适应 tester；后者选择的集合本身依赖先前回答。要么直接耦合完整决策树 transcript，要么把方法限制为非自适应并在定理中写明。

通信归约路线 ​

另一条路线把通信输入 $(x,y)$ 编码成待测对象，使 yes 通信输入产生性质成员、no 输入产生 far 对象。若一个 $q$-query tester 存在，双方模拟其 oracle：每次查询由拥有相应对象片段的一方回答，必要时交换地址或答案，从而得到低通信协议。

通信成本可能是 $q$ 乘每次回答 bit 数，也可能因 batch 查询、共享随机性或适应轮次改变。下界必须匹配生成协议的轮数和 coin model；只建立“查询一次大致像通信一次”的比喻不够。

常见失败边界 ​

No 分布中的对象必须以概率 $1$ far，或明确扣除不 far 质量；yes/no transcript 接近也必须对每棵允许的确定性树成立。分析一个自然 tester 的视图不能排除其他查询策略。

距离与表示不可丢失。同一稀疏图在 dense model 可能接近性质，在 bounded-degree model 却 far；把一个模型的 hard distribution 直接交给另一 oracle 会改变 no 支持。

单侧 tester 的拒绝 transcript 必须是确定 witness，常可利用证书结构得到不同下界；双侧 indistinguishability 允许两边都偶尔错。证明若使用 perfect completeness，不能无声推广到只要求 $2/3$ 接受的双侧模型，反向也一样。

参考资料

• Oded Goldreich, Introduction to Property Testing, Cambridge University Press, 2017, Chapters 10–11.
• Eric Blais, Joshua Brody, and Kevin Matulef, “Property Testing Lower Bounds via Communication Complexity,” Computational Complexity 21, 2012, pp. 311–358.
• Clément Canonne, “A Survey on Distribution Testing: Your Data Is Big. But Is It Blue?” Theory of Computing Graduate Surveys 9, 2020, lower-bound toolkit sections.
• Dana Ron, “Property Testing: A Learning Theory Perspective,” Foundations and Trends in Machine Learning 1(3), 2008, pp. 307–402.