## 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

- journal version
*Computational Complexity*, pages 1-47, 2016. - extended abstract in
*Proceedings of the Twenty-Ninth Annual IEEE Conference on Computational Complexity (CCC'14)*, pages 321-332, 2014. -
preliminary version in
*Electronic Colloquium on Computational Complexity*ECCC-TR13-163.