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 ( E (5−√2)/2 ) = O (ϵ 1.63 ). (A de Morgan, or unate, formula is a formula over the basis {∧, ∨, ¬}.) This improves a long‐standing result of O (ϵ 1.5 ) by Subbotovskaya and a recent improvement to O (ϵ (21−√73)/8 ) = O (ϵ 1.55 ) by Nisan and Impagliazzo. The New exponent yields an increased lower bound of n (7−√3)/2− o (1) = Ω( n 2.63 ) for the de Morgan formula size of a function in P defined by Andreev. This is the largest formula size lower bound known, even for functions in NP. © 1993 John Wiley & Sons, Inc.