We give a new and improved proof that the shrinkage exponent of dDe 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, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size of the function by a factor of $O(p^2)$. 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: \{0,1\}^n \to \{0,1\}$, which is in P, has formula size at least $\Omega(\frac{n^3}{\log^2 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. [FOCS, 2013]; we show that the functions defined by Komargodski et al. , $h_r: \{0,1\}^n \to \{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 Morgan formulae of size at most $\frac{n^3}{r^2 \mathrm{poly}\log n}$, for any parameter $r \le n^{1/3}$.

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$, $Q_2(f) \le O(\sqrt{L(f)})$, where $Q_2(f)$ is the bounded-error quantum query complexity of $f$, and $L(f)$ is the minimal size de Morgan formula computing $f$.

Changed title. Added section 7 which analyzes the Andreev's function more tightly, using a different distribution of random restrictions.

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: \{-1,1\}^n \to \{-1,1\}$, setting each variable out of $x_1, \ldots, x_n$ with probability $1-p$ to a randomly chosen constant, reduces the expected formula size of the function by a factor of $O(p^2)$. 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: \{-1,1\}^n \to \{-1,1\}$, which is in P, has formula size at least $\Omega(\frac{n^3}{\log^2 n \log^3\log n})$. This lower bound is tight up to the $\log^3\log n$ factor, and is the best known lower bound for functions in P. In addition, the functions defined by Komargodski et al. [FOCS, 2013], $h_r: \{-1,1\}^n \to \{-1,1\}$, which are also in P, cannot be computed correctly on a fraction greater than $1/2 + 2^{-r}$ of the inputs, by De Morgan formulae of size at most $\frac{n^3}{r^2 \mathrm{poly}\log n}$, for any parameter $r \le n^{1/3}$.

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$, $Q_2(f) \le O(\sqrt{L(f)})$, where $Q_2(f)$ is the bounded-error quantum query complexity of $f$, and $L(f)$ is the minimal size De Morgan formula computing $f$.