REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR12-062 | 16th October 2012 15:29

#### Average-Case Lower Bounds for Formula Size

Revision #2
Authors: Ilan Komargodski, Ran Raz
Accepted on: 16th October 2012 15:29
Keywords:

Abstract:

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 to TR12-062 | 18th May 2012 13:00

#### Average-Case Lower Bounds for Formula Size

Revision #1
Authors: Ilan Komargodski, Ran Raz
Accepted on: 18th May 2012 13:00
Keywords:

Abstract:

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

Changes to previous version:

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

### Paper:

TR12-062 | 17th May 2012 16:06

#### Average-Case Lower Bounds for Formula Size

TR12-062
Authors: Ilan Komargodski, Ran Raz
Publication: 17th May 2012 16:17
Keywords:

Abstract:

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

ISSN 1433-8092 | Imprint