Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

Average-Case Lower Bounds for Formula Size

RSS-Feed




Revision #2
Authors: Ilan Komargodski, Ran Raz
Accepted on: 16th October 2012 15:29
Downloads: 3469
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
Downloads: 2803
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


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