Fourier Concentration from Shrinkage

Russell Impagliazzo and Valentine Kabanets

Abstract

For a class $\mathcal{F}$ of formulas, general de Morgan or read-once de Morgan, the shrinkage exponent $\Gamma_{\mathcal{F}}$ is the parameter measuring the reduction in size of a formula $F\in\mathcal{F}$ after $F$ is hit with a random restriction. A Boolean function $f\colon \{0,1\}^n\to\{1,-1\}$ is Fourier-concentrated if, when viewed in the Fourier basis, $f$ has most of its total mass on ``low-degree'' coefficients. We show a direct connection between the two notions by proving that shrinkage implies Fourier concentration: for a shrinkage exponent $\Gamma_{\mathcal{F}}$, a formula $F\in\mathcal{F}$ of size $s$ will have most of its Fourier mass on the coefficients of degree up to about $s^{1/\Gamma_{\mathcal{F}}}$. More precisely, for a Boolean function $f\colon\{0,1\}^n\to\{1,-1\}$ computable by a formula of large enough size $s$ and for any parameter $t>0$, $$ \sum_{A\subseteq [n]\; :\; |A|\geq t} \hat{f}(A)^2 \leq exp\left(- \left(\frac{t^{\Gamma}}{s^{1+o(1)}} \right)^{\frac{1}{\Gamma-1}} \right), $$ where $\Gamma$ is the shrinkage exponent for the corresponding class of formulas: $\Gamma=2$ for de Morgan formulas, and $\Gamma=1/\log_2(\sqrt{5}-1)\approx 3.27$ for read-once de Morgan formulas. This Fourier concentration result is optimal, to within the $o(1)$ term in the exponent of $s$.

As a standard application of these Fourier concentration results, we get that subquadratic-size de Morgan formulas have negligible correlation with parity, and are learnable under the uniform distribution and lossily compressible in subexponential time. We also show the tight $\Theta(s^{1/\Gamma})$ bound on the average sensitivity of read-once formulas of size $s$, which mirrors the known tight bound $\Theta(\sqrt{s})$ on the average sensitivity of general de Morgan $s$-size formulas.

Versions