“KKL 定理与Friedgut junta 定理把超压缩用于离散导数,限制许多微弱坐标在低阶频谱中共同积累的质量。导数的低阶范数由其非零概率决定,超压缩因而把坐标影响转成可加的频谱质量界。”
形式陈述
存在绝对常数
影响与方差按Fourier–Walsh 页的约定计算。常数与
这比从
直觉
一个输出确实有波动的布尔规则,不可能让所有坐标都以比
证明中超压缩做了什么
常值函数已由零方差处理;以下假定
对
低阶项至少被一个导数计到,且其噪声权重
若
最后用
例子与边界
多数与 tribes 的差异
奇数
这比 KKL 的
把
这说明 KKL 的对数尺度在一般情形下不能提高到多数的
分布和量词的边界
取独裁者
偏置输入需要偏置版本的影响与常数,不能保留当前均匀结论而只替换样本分布。增加不相关变量也只会让右边下界变弱,并不迫使函数使用它们。
推论与应用
若函数对坐标具有传递对称性,各坐标影响相同,则 KKL 给
参考资料
- O’Donnell,《Analysis of Boolean Functions》§9.6 与 §4.2,KKL、总影响强化形式与 tribes。
- Kahn、Kalai 与 Linial,“The Influence of Variables on Boolean Functions”,FOCS 1988,§3,Theorem 3.1(所链接预印本 p. 5)。原文用
表达一般偏置结论;转换为本页 编码后, ,与 仅差绝对常数因子。