THE EFFECT OF RANDOM RESTRICTIONS ON FORMULA SIZE

We consider the formula size complexity of boolean functions over the base consisting of AND, OR, and inverted left perpendicular gates. In 1961 Subbotovskaya proved that, for any boolean function on n variables, setting all but a randomly chosen epsilonn variables to randomly chosen constants, reduces the expected complexity of the induced function by at least a factor of epsilon1.5. This fact was used by Subbotovskaya to derive a lower bound of OMEGA(n1.5) for the formula size of the parity function, and more recently by Andreev who exhibited a lower bound of OMEGAC(n2.5/log(O(1))(n)) for a function in P. We present the first improvement of Subbotovskaya's s result, showing that the expected formula complexity of a function restricted as above is at most an O(epsilon(gamma)) fraction of its original complexity, for gamma = (21 - square-root 73)/8 = 1.556... This allows us to give an improved lower bound of OMEGA(n2.556...) for Andreev's function. At the time of discovery, this was the best formula lower bound known for any function in NP.