KKL 影响定理

一个输出确实有波动的布尔规则，不可能让所有坐标都以比 $\log n/n$ 更小的概率起作用。变量可以分散权力，但布尔值约束与高阶矩控制限制了这种分散的程度。

证明中超压缩做了什么 ​

常值函数已由零方差处理；以下假定 $f$ 非常值，令 $m=\underset{i}{max}{\mathrm{Inf}}_i(f)>0$。离散导数 $D_{i}f=(f(x)-f(x^{\oplus i}))/2$ 只取 $0,\pm 1$。在超压缩不等式公理库布尔超压缩不等式Boolean hypercontractivity · Bonami-Beckner inequality给出布尔噪声算子从 Lp 到 Lq 收缩所需的精确噪声强度，并说明张量化如何消去维数依赖。中取 $p=3/2,q=2,\rho =1/\sqrt{2}$，得到

对 $i$ 求和，并把频谱分到次数 $d$ 以下与以上，便有

低阶项至少被一个导数计到，且其噪声权重 $2^{-|S|}\ge 2^{-d}$；高阶项则由总影响中的 $|S|\ge d+1$ 支付。

若 $m\le 2^{-6}$，取 $d=\lfloor {\log }_2(1/m)/6\rfloor$，两项合起来至多为 $CI(f)/\log \left(e/m\right)$。若 $m>2^{-6}$，同一形式由 $\mathrm{Var}(f)\le I(f)$ 并调大绝对常数得到。因此

最后用 $I(f)\le nm$。当 $m<n^{-1/2}$ 时，分母至少含 $\frac{1}{2}\log n$；当 $m\ge n^{-1/2}$ 时，利用 $\mathrm{Var}(f)\le 1$ 与 $\log n=O(\sqrt{n})$，也得到定理所需下界。这说明对数增益来自导数的稀疏值域，而不是简单平均。

多数与 tribes 的差异 ​

奇数 $n$ 的多数中，第 $i$ 票仅在其他 $n-1$ 票打平时关键，故

这比 KKL 的 $\log n/n$ 大，说明多数不是使最大影响最小的例子。

把 $n=mw$ 个变量分成 $m$ 组，每组 $w$ 位。tribes 在至少一组全为 $1$ 时输出 $1$，否则输出 $-1$。其输出 $-1$ 的概率为 $(1-2^{-w}{)}^m$；取 $m\approx (\log 2)2^w$，函数近似平衡。某位关键，当且仅当本组其他位全为 $1$，且其他组都不全为 $1$，所以

这说明 KKL 的对数尺度在一般情形下不能提高到多数的 $n^{-1/2}$。

分布和量词的边界 ​

取独裁者 $f=x_1$，其影响为 $(1,0,\dots ,0)$；KKL 不会要求无关坐标也有影响。取高度偏向常数的函数，则方差因子变小，定理相应允许更小影响。

偏置输入需要偏置版本的影响与常数，不能保留当前均匀结论而只替换样本分布。增加不相关变量也只会让右边下界变弱，并不迫使函数使用它们。

若函数对坐标具有传递对称性，各坐标影响相同，则 KKL 给 $I(f)\ge c\mathrm{Var}(f)\log n$。这把对称性与阈值跃迁联系起来，但要讨论随偏置改变的阈值宽度，还需配套偏置影响与微分公式。