We give an explicit function h:\{0,1\}^n\to\{0,1\} such that any deMorgan formula of size O(n^{2.499}) agrees with h on at most \frac{1}{2} + \epsilon fraction of the inputs, where \epsilon 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 \frac{1}{2} + \epsilon fraction of the inputs, where \epsilon is exponentially small (i.e. \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 \cite{And87}.

We give an explicit function h:\{0,1\}^n\to\{0,1\} such that any deMorgan formula of size O(n^{2.499}) agrees with h on at most \frac{1}{2} + \epsilon fraction of the inputs, where \epsilon is exponentially small (i.e. \epsilon = 2^{-n^{\Omega(1)}}). The same technique also shows that any boolean formula of size O(n^{1.999}) over the complete basis, agrees with h on at most \frac{1}{2} + \epsilon fraction of the inputs, where \epsilon is exponentially small (i.e. \epsilon = 2^{-n^{\Omega(1)}}). Previously, such lower bounds were only obtained for exact computation.

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 \cite{And87}.

Added reference to Santhanam's work (FOCS 2010).

We give an explicit function h:\{0,1\}^n\to\{0,1\} such that any deMorgan formula of size O(n^{2.499}) agrees with h on at most \frac{1}{2} + \epsilon fraction of the inputs, where \epsilon is exponentially small (i.e. \epsilon = 2^{-n^{\Omega(1)}}). Previous lower bounds for formula size were obtained for exact computation.

The same technique also shows that any boolean formula of size O(n^{1.999}) over the complete basis, agrees with h on at most \frac{1}{2} + \epsilon fraction of the inputs, where \epsilon is exponentially small (i.e. \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 \cite{And87}.