Average-case lower bounds for formula size
Ilan Komargodski, Ran Raz · 2013
We give an explicit function h:{0,1}n->{0,1} such that any deMorgan formula of size O(n2.499) agrees with h on at most 1/2 + ε fraction of the inputs, where ε is exponentially small (i.e. ε = 2-nΩ(1)). We also show, using the same technique, that any boolean formula of size O(n1.999) over the complete basis, agrees with h on at most 1/2 + ε fraction of the inputs, where ε is exponentially small (i.e. ε = 2-nΩ(1)). Our construction is based on Andreev's Ω(n2.5-o(1)) formula size lower bound that was proved for the case of exact computation.