ECCC-Report TR12-062https://eccc.weizmann.ac.il/report/2012/062Comments and Revisions published for TR12-062en-usTue, 16 Oct 2012 15:29:09 +0200
Revision 2
| Average-Case Lower Bounds for Formula Size |
Ilan Komargodski,
Ran Raz
https://eccc.weizmann.ac.il/report/2012/062#revision2We 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}.Tue, 16 Oct 2012 15:29:09 +0200https://eccc.weizmann.ac.il/report/2012/062#revision2
Revision 1
| Average-Case Lower Bounds for Formula Size |
Ilan Komargodski,
Ran Raz
https://eccc.weizmann.ac.il/report/2012/062#revision1We 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}.Fri, 18 May 2012 13:00:26 +0300https://eccc.weizmann.ac.il/report/2012/062#revision1
Paper TR12-062
| Average-Case Lower Bounds for Formula Size |
Ilan Komargodski,
Ran Raz
https://eccc.weizmann.ac.il/report/2012/062We 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}.Thu, 17 May 2012 16:17:51 +0300https://eccc.weizmann.ac.il/report/2012/062