The Shrinkage Exponent of de Morgan Formulas is 2
Johan HÅ stad · SIAM Journal on Computing · 1998
We prove that if we hit a de Morgan formula of size L with a random restriction from R p , then the expected remaining size is at most $O(p^2(\log \frac {1}{p})^{3/2}L+p\sqrt L)$. As a corollary we obtain an $\Omega(n^{3-o(1)})$-formula-size lower bound for an explicit function in P. This is the strongest known lower bound for any explicit function in NP.