块敏感度

单点敏感度理路布尔函数敏感度Sensitivity of Boolean functions · Boolean sensitivity统计在固定输入处单独翻转一个坐标会改变函数值的 Hamming 邻居数量。只看沿 cube 边移动一步是否越过输出边界；块敏感度允许若干坐标协同翻转，再从这些改变方向中选取互不占用同一坐标的最大 packing。它因此捕捉“单独无效、合在一起有效”的局部结构，同时让每个块代表一份独立坐标资源。

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

考虑四变量函数

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

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

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

与敏感度的关系 ​

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

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

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

证书必须击中每个块 ​

固定输入 $x$，取任意证书理路证书复杂度Certificate complexity of Boolean functions · Boolean certificate complexity用足以强制某个固定输入函数值的最少已知坐标数，分别度量 0-证书与 1-证书。坐标集 $I$。若某个敏感块 $B$ 与 $I$ 不交，则 $x^{\oplus B}$ 在全部证书坐标上与 $x$ 一致，却具有相反函数值，矛盾。因此证书必须与每个敏感块相交。

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

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

最小块与冗余 ​

构造块族时可以把每个敏感块缩到包含意义下极小：它没有仍然敏感的真子集。有限性保证这样的子块存在，缩小各块也保留两两不交。极小性不是块敏感度定义的要求，却能去掉不必要的坐标。

只检查“删去任意单个坐标后都不敏感”还不够。例如三位奇偶函数在 000 处，块 $\{1,2,3\}$ 敏感，删去任一坐标后剩下两位，翻转结果又变回偶数，因而不敏感；但其中每个单元素子集仍敏感，所以这个三元素块并非包含意义下极小。

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

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

边界与使用口径 ​

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

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

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

噪声敏感度理路噪声稳定性与噪声敏感性Noise stability · Noise sensitivity用噪声前后输出的相关与翻转概率，区分单个函数的稳定程度和一族函数的噪声敏感极限。让各坐标独立随机翻转，考察输出变化概率；块敏感度则在同一个指定输入附近寻找互不相交的翻转块。一个大的敏感块在两种度量中受到的权重完全不同，因此块数不能直接代替随机扰动概率或其规模极限。