261 Boolean Analysis — Threshold
261.1 Overview
Linear threshold functions have Fourier tails controlled by a reciprocal-square degree cutoff. An optimized influence threshold gives junta approximation with polynomial dependence on total influence.
261.2 Declarations
There exists an absolute \(B\ge 1\) such that for every linear threshold function \(f:\{ 0,1\} ^n\to \{ -1,1\} \) and \(0\lt \varepsilon \le 1/2\), there is \(k\in \mathbb N\) with \(k\le B/\varepsilon ^2\) and \(\sum _{|S|\gt k}\widehat f(S)^2\le \varepsilon \) under the uniform cube law.
Let \(B\ge 1\), \(0\lt \varepsilon ,\eta \le 1/2\), and \(k\in \mathbb N\) with \(k\le B/\varepsilon ^2\). Then \(1/(\varepsilon (\eta /(2+\eta ))^k)^{1+\eta }\le (1/\eta )^{200B/\varepsilon ^2}\).
There exists an absolute \(C\gt 0\) such that for every linear threshold function \(f:\{ 0,1\} ^n\to \{ -1,1\} \) under the uniform law and \(0\lt \varepsilon ,\eta \le 1/2\), there exist \(J\subseteq [n]\) and \(h:\{ 0,1\} ^n\to \{ -1,1\} \) depending only on \(J\) with \(|J|\le I(f)^{2+\eta }(1/\eta )^{C/\varepsilon ^2}\) and \(\Pr (f\ne h)\le \varepsilon \). For a real cube function \(h\), define \(I_i(h)=\tfrac 14\mathbb E_x(h(x)-h(x^{(i)}))^2\), where \(x^{(i)}\) flips coordinate \(i\) and \(\mathbb E_x\) is uniform expectation, and \(I(h)=\sum _{i=0}^{n-1}I_i(h)\).