The shrinkage exponent is 2
Johan Håstad · 2002
We prove that if we hit a formula of size L with a random restriction from R/sub p/ then the expected remaining size is at most O(p/sup 2/(log p)/sup 3/2/L). As a corollary we obtain a R(n/sup 3-O(1)/) formula size lower bound for an explicit function in NP.>