布尔函数敏感度

点敏感度 ​

对 $x\in \{0,1{\}}^n$，记 $x^{\oplus i}$ 为只翻转第 $i$ 位所得输入。布尔函数 $f$ 在 $x$ 处的敏感坐标集为

$$S(f,x)=\{i\in [n]:f(x)\ne f(x^{\oplus i})\},$$

点敏感度为

$$s(f,x)=|S(f,x)|.$$

它只查看Hamming 距离公理库Hamming 距离Hamming distance两个等长字在对应位置不同的坐标数。恰为 $1$ 的邻居，并数其中多少条 cube 边跨越了 0/1 输出边界。全局敏感度取最坏输入

$$s(f)=\underset{x}{max}s(f,x),$$

还可分成 $s_b(f)=\underset{x:f(x)=b}{max}s(f,x)$。

对偏函数 $f:S\to \{0,1\}$，只有 $x,x^{\oplus i}\in S$ 时该翻转才是合法邻边。把 promise 外的值任意补成 0 或 1 会人为增加或删除敏感坐标，因此 partial sensitivity 必须声明采用的合法域。

OR 上的状态变化 ​

对 ${\mathrm{OR}}_n$，在 $x=0^n$ 处翻转任意一个坐标都会从 $0$ 变为 $1$，所以

$$s({\mathrm{OR}}_n,0^n)=n.$$

若 $x$ 恰有一个 $1$，只有翻转那个唯一的 $1$ 才会把输出变回 $0$，点敏感度为 $1$。若 $x$ 至少有两个 $1$，翻转任一单独坐标后仍至少留一个 $1$，点敏感度为 $0$。

因此同一函数在三类输入上呈现 $n,1,0$ 三种局部边界形状，而全局值只保留最大者 $s({\mathrm{OR}}_n)=n$。只报告全局敏感度会丢掉输入依赖图像；证明若需要 0/1 两侧，应使用 $s_0,s_1$。

与证书、查询的基本关系 ​

固定输入 $x$ 的任何证书都必须包含每个敏感坐标 $i$。若证书遗漏 $i$，则 $x^{\oplus i}$ 与 $x$ 在全部证书坐标上一致，却拥有相反函数值，违背证书定义。于是

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

再结合确定性决策树路径形成证书，得到

$$s(f)\le C(f)\le D^{\mathrm{query}}(f).$$

这条链给出查询下界，却不声称查询算法只需检查敏感坐标。算法事前不知道当前输入，也不知道哪些坐标在当前点敏感；OR 的全零输入恰好同时使三个量都达到 $n$。

一个局部边界图像 ​

把 Boolean cube 的每个输入当作顶点，Hamming 距离 $1$ 的输入间连边，并按 $f$ 值染成两色。$s(f,x)$ 就是从 $x$ 出发通向异色顶点的边数。敏感度因此衡量的是决策边界在某个顶点周围有多少个坐标方向。

它不计算距离更远的协同变化。若单独翻转每一位都不改输出，但同时翻转两位会改输出，点敏感度看不到这组变化；块敏感度公理库块敏感度Block sensitivity of Boolean functions · Boolean block sensitivity在固定输入处寻找最多个互不相交的坐标块，使整体翻转任一块都会改变函数值。正是为捕捉互不相交的多坐标翻转而引入。

不等于一般 Lipschitz 常数 ​

若输出使用离散距离 $|f(x)-f(y)|$、输入使用 raw Hamming 距离，则每个 Boolean function 都满足

$$|f(x)-f(y)|\le d_H(x,y),$$

所以任何非常值函数的最优全局 Lipschitz 常数都是 $1$。这个常数只问单条边变化幅度最多多大，而敏感度数同一顶点有多少条边发生变化，两者表达不同信息。

若输入距离改为 normalized Hamming $d_H/n$，非常值函数的相邻跳变会给 Lipschitz 常数至少 $n$；它仍不会区分一个敏感方向与 $n$ 个敏感方向。不能因为两个概念都讨论“局部变化”就把数值互换。

敏感度也不是导数：Boolean cube 没有连续小步，翻转幅度固定为一位。把函数延拓到 $[0,1{]}^n$ 后的梯度依赖所选延拓，不由原布尔函数唯一决定。

失败边界 ​

敏感坐标必须在同一个基点 $x$ 上统计。分别为每个坐标挑一个最有利输入再相加，会得到另一种量，并不能证明存在某个输入具有那么多敏感方向。

全局最大值也可能由极少数输入达到。若算法输入来自分布，平均敏感度或 influence 更适合描述典型扰动；$s(f)$ 仍是最坏局部组合量，不包含输入概率。

最后，单比特敏感度较小不表示函数可用同样少的查询计算。远距离或成块变化可能隐藏更多复杂性；需要比较其他度量时，应保留 total/partial、点值/全局和 0/1 侧的限定。

参考资料

• 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, Chapters 2 and 8.