Friedgut junta 定理

总影响小表示平均而言，输出很少因单坐标翻转而改变。这迫使函数的大部分可预测结构集中在少数重要坐标上。它仍可以在罕见输入处依赖其他坐标，所以结论是分布意义下的近似，不是精确删去全部弱变量。

证明的两道筛选 ​

先处理极小总影响。记 $I=I(f)$；若 $I\le \epsilon$，少数输出的概率 $p\le 1/2$ 满足 $2p\le 4p(1-p)=\mathrm{Var}(f)\le I$，所以直接取多数输出常量即可。

以下取 $I>\epsilon$，令 $d=\lceil 4I/\epsilon \rceil$。高阶质量满足 $\sum _{|S|>d}\hat{f}(S{)}^2\le I/(d+1)<\epsilon /4$。再令

显然 $|J|\le I/\tau$。对 $J$ 外的离散导数用 $p=3/2,q=2,\rho =1/\sqrt{2}$ 的超压缩公理库布尔超压缩不等式Boolean hypercontractivity · Bonami-Beckner inequality给出布尔噪声算子从 Lp 到 Lq 收缩所需的精确噪声强度，并说明张量化如何消去维数依赖。，得到

每个被删低阶项至少包含一个 $J$ 外坐标，因而出现在右侧某个导数中。两次筛选合计损失至多 $\epsilon /2$；而 $I/\tau =64I^4{8}^d/{\epsilon }^3\le \exp \left(CI/\epsilon \right)$，因为 $I/\epsilon >1$、$\epsilon <1/2$，多项式因子也可吸收到这个绝对常数指数中。

对保留坐标作条件平均公理库条件期望Conditional expectation以信息分组的加权平均建立条件期望直觉，再连接测度定义、最小均方预测、塔式性质和可计算反例。 $h(x_J)=\mathbb{E}[f(X)\mid X_J=x_J]$，它恰保留 $S\subseteq J$ 的 Fourier 项。最后令 $g=\mathrm{sign}h$，并固定零点规则；若 $f\ne g$，则 $|f-h|\ge 1$，因此分类错误受丢失的平方质量控制。

使用全部坐标，仍接近常量 ​

令 $f=1$ 当且仅当全部 $n$ 个坐标为 $1$，其余输出 $-1$。每个坐标影响为 $2^{-(n-1)}$，所以 $I(f)=n{2}^{-(n-1)}$ 很小。函数精确地依赖每一位，但常量 $g=-1$ 的错误率仅为 $2^{-n}$。

例如 $n=10$，总影响为 $10/512\approx 0.01953$，常量误差为 $1/1024\approx 0.000977$。当目标误差为 $0.01$ 时，零坐标近似已经足够；定理没有要求找到所有精确相关变量。

低次数与少坐标不同 ​

低次数多项式可以同时涉及很多变量。三位多数次数为三且使用三位；更多位多数的总影响随 $\sqrt{n}$ 增长，定理给出的 junta 大小不再是固定常数。频谱截断与坐标删减各自需要不同条件，不能只由“低阶项很多”推出小 junta。

当 $\epsilon$ 缩小时，指数界可能迅速超过 $n$，此时直接取 $g=f$ 更好。存在性定理也不自动提供高效寻找 $J$ 的算法；查询模型与可计算性需另外分析。

定理为学习提供结构压缩依据：一旦找到了正确的少量坐标，只需学习它们上的真值表。但表本身仍可能有 $2^{|J|}$ 项，指数大小的结构界未必能产生现实可行的学习器。

本页限于均匀乘积分布。偏置靠近零或一时，变量稀有事件的结构会变化，需使用带分布依赖常数的版本。