Friedgut junta inequality
= Friedgut junta inequality
{c}
If $f:\{-1,1\}^n\to\{-1,1\}$ satisfies $\lVert f^{\leq k}\rVert_2^2\geq1-\varepsilon$, then it has a real-valued $J$-junta approximation $g$ with $\lVert f-g\rVert_2^2\leq2\varepsilon$ and
$$
|J|\leq\frac{3^{2k}\mathbf I(f)^3}{\varepsilon^2}.
$$