Average-Case Lower Bounds for Formula Size

We give an explicit function h : {0,1}(n) -> {0, 1} such that any deMorgan formula of size O (n(2.499)) agrees with h on at most 1/2+ epsilon fraction of the inputs, where e is exponentially small (i.e. epsilon = 2(-n Omega(1))). We also show, using the same technique, that any boolean formula of size O(n(1.999)) over the complete basis, agrees with h on at most 1/2 + epsilon fraction of the inputs, where epsilon is exponentially small (i.e. epsilon = epsilon = 2(-n Omega(1))). Our construction is based on Andreev's Omega(n(2.5-o(1))) formula size lower bound that was proved for the case of exact computation [2].