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:−11n−11 , setting each variable out of x1xn 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 H{\aa}stad [SIAM J. C., 1998] by removing logarithmic factors.

As a consequence of our results, the function defined by Andreev [MUMB., 1987], A:−11n−11 , which is in P, has formula size at least (n3log2nlog3logn). This lower bound is tight up to the log3logn factor, and is the best known lower bound for functions in P. In addition, the functions defined by Komargodski et al. [FOCS, 2013], hr:−11n−11 , which are also in P, cannot be computed correctly on a fraction greater than 12+2−r of the inputs, by De Morgan formulae of size at most n3r2polylogn, for any parameter rn13 .

The proof relies on a result from quantum query complexity by Laplante et al. [CC, 2006], H{\o}yer et al. [STOC, 2007] and Reichardt [SODA, 2011]: for any Boolean function f, Q2(f)O(L(f)) , where Q2(f) is the bounded-error quantum query complexity of f, and L(f) is the minimal size De Morgan formula computing f.