Fourier Concentration from Shrinkage
Russell Impagliazzo, Valentine Kabanets · 2014
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}n→ {1, -1} computable by a de Morgan formula of size s, we show that Σ f̂ (A)2≤ exp(√sϵ/3), A⊆[n] : |A| > s1/Γ+ϵwhere Γ is the shrinkage exponent for the corresponding class of formulas: Γ = 2 for de Morgan formulas, and Γ = 1/log2(√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 Θ(s1/Γ) 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.