性质测试下界方法

性质测试下界的共同图像，是让 yes 与 no 两个世界在少量局部观察下保持同样面貌。困难分布先把随机算法化成确定性决策树的平均问题，transcript 距离再衡量这棵树究竟获得了多少区分信息；如果大部分执行仍看到相同答案历史，叶上的任何判决都会在至少一侧出错。

自适应查询没有破坏这幅图，但要求证明随着历史在线延伸。不能只说每组固定坐标的边缘分布接近，因为算法会根据此前答案选择下一坐标；真正需要控制的是整条决策树路径，或给出能同时延伸 yes/no 隐藏对象的耦合。

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

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

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

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

当 $\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 因而给出随机查询下界

与随机抽坐标的 $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$ 接受的双侧模型，反向也一样。