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, for This 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.