Russell Impagliazzo (Theory Seminar W14)

impagliazzo.jpg"Fourier Concentration from Shrinkage"
Russell Impagliazzo
Monday, February 3rd, 2014, 2:00pm
EBU3B, Room 4140
For Boolean functions computed by de Morgan formulas of subquadratic 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

\sum{\hat{f}(A)^2 : A \subseteq [n], |A|>s^{1/Gamma + epsilon}} <= -exp(−s/3)

where Gamma is the shrinkage exponent for the corresponding class of formulas: Gamma=2 for de Morgan formulas, and Gamma=3.27 for read-once de Morgan formulas. We prove that this Fourier concentration is essentially optimal. As an application, we get that subquadratic-size de Morgan formulas have negligible correlation with parity, and are learnable under the uniform distribution, and also lossily compressible, in subexponential time. We also prove that the average sensitivity of a read-once function f on n variables is at most n^{1/Gamma+o(1)}, and is at least Omega(n^{1/Gamma}) .

Joint work with Valentine Kabanets (paper link