块敏感度

敏感块 ​

对 $B\subseteq [n]$，记 $x^{\oplus B}$ 为同时翻转 $x$ 在 $B$ 中全部坐标所得输入。若

$$f(x)\ne f(x^{\oplus B}),$$

则 $B$ 是 $f$ 在 $x$ 处的敏感块。点块敏感度定义为最多能同时选出多少个两两不交的敏感块：

$$bs(f,x)=max\{k:\begin{array}{l}{B}_1,\dots ,B_k\subseteq [n]\text{ 两两不交},\\ f(x)\ne f(x^{\oplus B_j})\text{ 对每个 }j\end{array}\}.$$

全局值为 $bs(f)=\underset{x}{max}bs(f,x)$，也可按 $f(x)=0$ 或 $1$ 定义 $b{s}_0,b{s}_1$。对偏函数，还必须要求每个 $x^{\oplus B_j}$ 落在 promise 域中；块翻转不能借用未定义输入。

集合不交公理库集合运算Set operations · Union, intersection, difference并、交、差与补集等按成员条件构造新集合的运算。条件不是排版便利，而是度量的核心。它确保每个块代表一份坐标资源互不重叠的独立改变方向；允许重复使用同一关键坐标会把同一障碍无限复制。

单比特不敏感、成块却敏感 ​

考虑四变量函数

$$f(x)=(x_1\wedge x_2)\vee (x_3\wedge x_4).$$

在 $x=0000$ 处，翻转任意一个 bit 都只得到单个 $1$，两个 AND 项仍为 $0$，所以

$$s(f,0000)=0.$$

但块 $B_1=\{1,2\}$ 翻转后得到 1100，第一项变为 $1$；块 $B_2=\{3,4\}$ 翻转后得到 0011，第二项变为 $1$。两块不交，因此

$$bs(f,0000)\ge 2.$$

任一敏感块至少含两个坐标，而四个坐标至多容纳两个互不相交的这种块，故这里恰有 $bs(f,0000)=2$。这个例子展示块敏感度不是把单比特敏感度换个单位，而是捕捉必须协同翻转才越过输出边界的结构。

与敏感度的关系 ​

每个敏感坐标 $i$ 都给出单元素敏感块 $\{i\}$，而不同坐标对应的单元素块自动不交，所以逐点有

$$s(f,x)\le bs(f,x),$$

进而 $s(f)\le bs(f)$。不等式可以严格，如上例在 0000 处为 $0<2$。

反向不能通过把每块任选一个代表坐标得到。一个块之所以敏感，可能恰是所有坐标共同翻转的结果；只翻代表坐标未必改变输出。把块压成单点会销毁要测量的协同效应。

证书必须击中每个块 ​

固定输入 $x$，取任意证书坐标集 $I$。若某个敏感块 $B$ 与 $I$ 不交，则 $x^{\oplus B}$ 在全部证书坐标上与 $x$ 一致，却具有相反函数值，矛盾。因此证书必须与每个敏感块相交。

若 $B_1,\dots ,B_k$ 两两不交，一个证书坐标最多击中其中一个块，所以 $|I|\ge k$。最大化块族、最小化证书得到

$$bs(f,x)\le C(f,x).$$

结合确定性路径证书可得 $bs(f)\le C(f)\le D^{\mathrm{query}}(f)$。这条下界链只使用互不相交；若允许块重叠，一个证书坐标可同时击中许多块，计数证明就会失效。

最小块与冗余 ​

构造块族时可以把每个敏感块缩到 inclusion-minimal：删除任意坐标后不再敏感。最小性不是定义要求，但能暴露真正协同的一组坐标，并避免把无关位置塞进块中制造名词堆叠。

最小敏感块之间仍可能重叠，所以不能把“每块都不可再缩”误认为“块族自动不交”。优化 $bs(f,x)$ 仍需从候选块中选择一组 packing，而不是统计全部最小块数量。

最大 packing 也未必唯一：两组不同块族可以拥有相同块数，却覆盖不同坐标。$bs(f,x)$ 只记录最优数量；若证明依赖具体块的大小或位置，必须保留所选 witness，而不能只剩一个整数。

边界与使用口径 ​

块敏感度一次翻转整个块，但只比较起点 $x$ 与终点 $x^{\oplus B}$；它不要求沿逐位翻转的中间路径保持函数值。若研究路径上首次越界，得到的是不同的局部过程量。

块可以大小不同，度量只数块数而不数总翻转坐标。若任务关心最少编辑数量，应使用 Hamming 距离；一个巨大的敏感块在 $bs$ 中仍只贡献 $1$。

对随机输入分布，$bs(f)$ 仍取最坏点，不表示典型输入有许多敏感块。比较平均 influence、噪声稳定性或随机查询复杂度时，需要额外桥梁，不能把块 packing 数直接当作概率。

参考资料

• Noam Nisan, “CREW PRAMs and Decision Trees,” SIAM Journal on Computing 20(6), 1991, pp. 999–1007.
• Harry Buhrman and Ronald de Wolf, “Complexity Measures and Decision Tree Complexity: A Survey,” Theoretical Computer Science 288(1), 2002, pp. 21–43.
• Ryan O'Donnell, Analysis of Boolean Functions, Cambridge University Press, 2014, Chapter 2.