Avishay Tal: Shrinkage of De Morgan Formulae by Spectral Techniques

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→{0,1}, setting each variable out of x1,…,xn with probability 1−p to a randomly chosen constant, reduces the expected formula size of the function by a factor of O(p2). 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.