Fourier Concentration from Shrinkage

For Boolean functions computed by de Morgan formulas of sub quadratic size or read-once de Morgan formulas, we prove a sharp concentration of the Fourier mass on "small-degree" coefficients. For a Boolean function f : {0, 1}ⁿ → {1, -1} computable by a de Morgan formula of size s, we show that Σ f̂ (A)² ≤ exp(√s^ϵ/3), A⊆[n] : |A| > s^1/Γ+ϵ where Γ is the shrinkage exponent for the corresponding class of formulas: Γ = 2 for de Morgan formulas, and Γ = 1/log₂(√5-1) ≈ 3.27 for read-once de Morgan formulas. We prove that this Fourier concentration is essentially optimal. As an application, we get that sub quadratic-size de Morgan formulas have negligible correlation with parity, and are learnable under the uniform distribution, and also lossily compressible, in sub exponential time. Finally, we establish the tight Θ(s^1/Γ) bound on the average sensitivity of read-once formulas of size s, this mirrors the known tight bound Θ(√s) on the average sensitivity of general de Morgan formulas of size s.