Theory Lunch

Shrinkage of De Morgan Formulae by Spectral Techniques

Avishay Tal

October 15, 2014

We give a new and improved proof that the shrinkage exponent of De Morgan formulae is 2. Namely, we show that for any Boolean function $f:\{0,1{\}}^n\to \{0,1\}$, setting each variable out of $x_1,\dots ,x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size of the function by a factor of $O\left(p^2\right)$. This result is tight and improves the work of Hastad [SIAM J. C., 1998] by removing logarithmic factors.

As a consequence of our results, we strengthen the best formula size lower bounds for functions in P. The proof mainly uses discrete Fourier analysis, and relies on a result from quantum query complexity by Laplante et al. [CC, 2006], Hoyer et al. [STOC, 2007] and Reichardt [SODA, 2011].

No prior knowledge about quantum computing is assumed.