布尔函数敏感度

把 Boolean cube 按函数值染成两色，$s(f,x)$ 就是在顶点 $x$ 周围数有多少条坐标边跨过颜色边界。它描述的是决策边界在一个点附近张开多少个方向，而不是边界离该点多远，也不是函数在典型输入上的平均变化。

单坐标视野既使定义清晰，也留下盲区。若任何一位单独翻转都无效，若干位协同翻转却改变输出，敏感度在该点仍为零；块敏感度理路块敏感度Block sensitivity of Boolean functions · Boolean block sensitivity在固定输入处寻找最多个互不相交的坐标块，使整体翻转任一块都会改变函数值。正是把局部探针从一条边扩展到互不相交的坐标块。

OR 上的状态变化 ​

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

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

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

不等于一般 Lipschitz 常数 ​

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

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

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

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

失败边界 ​

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

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

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

敏感度通过 $s\le C\le D$ 给出最直接的确定性查询下界：在某个输入附近有 $k$ 个单独翻转就能改值，任何确认该输入输出的证书都必须覆盖这 $k$ 个坐标。这个推论保留同一基点，不能把不同输入上的敏感方向拼成一个更大的证书障碍。

在研究典型噪声或分布扰动时，average sensitivity 与 influence 往往比最坏 $s(f)$ 更贴近问题；在研究协同翻转时，则应转向 block sensitivity。选择这些变体不是换一种描述风格，而是在更换局部邻域与聚合量词。

均匀输入下，Fourier 影响公式理路Fourier–Walsh 展开与影响度Fourier-Walsh expansion · Boolean Fourier analysis在均匀布尔立方体上用字符正交基展开函数，把方差和坐标影响写成 Fourier 系数的平方和。把坐标改变输出的概率写成所有含该坐标系数的平方和。KKL 定理理路KKL 影响定理KKL theorem在均匀立方体上，以方差和维数约束最大坐标影响，并用 tribes 展示对数因子的必要尺度。进一步保证非平凡布尔函数至少有一个影响达到方差乘 $\log n/n$ 的量级；它不要求每个输入都敏感。

若同时随机翻转多个坐标，噪声稳定性理路噪声稳定性与噪声敏感性Noise stability · Noise sensitivity用噪声前后输出的相关与翻转概率，区分单个函数的稳定程度和一族函数的噪声敏感极限。通过 ${\rho }^{|S|}$ 加权描述整条扰动曲线。固定均值并要求所有坐标影响趋小时，多数最稳定定理理路多数最稳定定理Majority is stablest theorem在均匀输入、固定均值和所有坐标影响足够小时，以高斯半空间给出噪声稳定性的渐近最优上界。给出高斯半空间的渐近上界。这里的平均量与本页的最坏点敏感度有不同的量词。