Shrinkage of de Morgan formulae under restriction

It is shown that a random restriction leaving only a fraction ∈ of the input variables unassigned reduces the expected de Morgan formula size of the induced function by a factor of O(∈ ^1.63). This is an improvement over previous results. The new exponent yields an increased lower bound of approximately n^2.63 for the de Morgan formula size of a function in P defined by A.E. Andreev (1987). This is the largest lower bound known, even for functions in NP