The effect of random restrictions on formula size

We consider the formula size complexity of boolean functions over the base consisting of ∧, ∨, and ¬ gates. In 1961 Subbotovskaya proved that, for any boolean function on n variables, setting all but a randomly chosen ϵ n variables to randomly chosen constants, reduces the expected complexity of the induced function by at least a factor. This fact was used by Subbotovskaya to derive a lower bound of Ω( n 1.5 ) for the formula size of the parity function, and more recently by Andreev who exhibited at lower bound of Ω C ( n 2.5 /log O (1) ( n )) for a function in P . We present the first improvement of Subbotovskaya's result, showing that the expected formual complexity of a function restricted as above is at most an O (ϵ γ ) franction of its original complexity, forThis allows us to give an improved lower bound of Ω( n 2.556… ) for Andreev's function. At the time of discovery, this was the best formula lower bound known for any function in NP. © 1993 John Wiley & Sons, Inc.