Revision #2 Authors: Ilan Komargodski, Ran Raz

Accepted on: 16th October 2012 15:29

Downloads: 2957

Keywords:

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}.

Revision #1 Authors: Ilan Komargodski, Ran Raz

Accepted on: 18th May 2012 13:00

Downloads: 2693

Keywords:

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).

TR12-062 Authors: Ilan Komargodski, Ran Raz

Publication: 17th May 2012 16:17

Downloads: 3516

Keywords:

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}.