Let \(C\) be a Boolean circuit on \(n \ge 1\) input bits with depth at most \(d\), size at most \(s\), and gate fan-in at most \(w\), where \(d \ge 2\) and \(s, w \ge 1\). Let \(l \ge 1\) and \(t\) be natural numbers, and let \(\varepsilon \gt 0\) be a real number such that the switching parameters satisfy \(s \cdot 2^{-l} \le \varepsilon /2\) and \(2^{-t} \le \varepsilon /2\). Write \(\delta = \frac{1}{40w}\bigl(\frac{1}{40l}\bigr)^{d-2}\) for the composed restriction rate, \(\sigma \) for the sign encoding of a bit (\(\sigma (\mathtt{false}) = 1\), \(\sigma (\mathtt{true}) = -1\)), and \(\widehat{\sigma \circ C}(U)\) for the Fourier–Walsh coefficient at \(U \subseteq [n]\) of the \(\pm 1\)-encoding of the function computed by \(C\). Then the Fourier weight above degree \(3(t+1)/\delta \) is small:

Let \(C\) be a Boolean circuit on \(n \ge 1\) input bits with depth at most \(d\), size at most \(s\), and gate fan-in at most \(w\), where \(d \ge 2\) and \(s, w \ge 1\), and let \(\varepsilon \) be a real number with \(0 \lt \varepsilon \le 1\). Set \(l = \lceil \log _2(2s/\varepsilon ) \rceil \) and \(t = \lceil \log _2(2/\varepsilon ) \rceil \), and write \(\delta = \frac{1}{40w}\bigl(\frac{1}{40l}\bigr)^{d-2}\), \(\sigma \) for the sign encoding of a bit (\(\sigma (\mathtt{false}) = 1\), \(\sigma (\mathtt{true}) = -1\)), and \(\widehat{\sigma \circ C}(U)\) for the Fourier–Walsh coefficient at \(U \subseteq [n]\) of the \(\pm 1\)-encoding of the function computed by \(C\). Then

that is, the Fourier spectrum of \(\sigma \circ C\) is concentrated — up to Chernoff tail terms that vanish as \(n \to \infty \) — below degree \(3\bigl(\lceil \log _2(2/\varepsilon )\rceil + 1\bigr) \cdot 40 w \, \bigl(40\lceil \log _2(2s/\varepsilon )\rceil \bigr)^{d-2} = O\! \left(w \log (s/\varepsilon )^{d-2} \log (1/\varepsilon )\right)\).