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}ⁿ → {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(p²). This result is tight and improves the work of Hastad [SIAM J. C., 1998] by removing logarithmic factors. As a consequence of our results, the function defined by Andreev [MUMB., 1987], A : {0, 1}ⁿ → {0, 1}, which is in P, has formula size at least Ω(n^3/log² n log³ log n). This lower bound is tight (for the function A) up to the log³ log n factor, and is the best known lower bound for functions in P. In addition, we strengthen the average-case hardness result of Komargodski et al.; we show that the functions defined by Komargodski et al., h_r : {0, 1}ⁿ → {0, 1}, which are also in P, cannot be computed correctly on a fraction greater than 1/2 + 2^-r of the inputs, by De n³ Morgan formulae of size at most n³/r²poly logⁿ, for any parameter r ≤ n^1/3. The proof relies on a result from quantum query complexity by Laplante et al. [CC, 2006], Høyer et al. [STOC, 2007] and Reichardt [SODA, 2011]: for any ´/´ Boolean function f, Q₂(f) ≤ O( L(f)), where Q₂(f) is the bounded-error quantum query complexity of f, and L(f) is the minimal size De Morgan formula computing f.