ECCC-Report TR13-058https://eccc.weizmann.ac.il/report/2013/058Comments and Revisions published for TR13-058en-usSun, 14 May 2017 08:58:07 +0300
Revision 2
| Improved Average-Case Lower Bounds for De Morgan Formula Size |
Ilan Komargodski,
Ran Raz,
Avishay Tal
https://eccc.weizmann.ac.il/report/2013/058#revision2We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every De Morgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs.
Our technical contributions include a theorem that shows that the ``expected shrinkage'' result of Hästad (SIAM J. Comput., 1998) actually holds with very high probability (where the restrictions are chosen from a certain distribution that takes into account the structure of the formula), using ideas of Impagliazzo, Meka and Zuckerman (FOCS, 2012).Sun, 14 May 2017 08:58:07 +0300https://eccc.weizmann.ac.il/report/2013/058#revision2
Revision 1
| Improved Average-Case Lower Bounds for DeMorgan Formula Size |
Ilan Komargodski,
Ran Raz,
Avishay Tal
https://eccc.weizmann.ac.il/report/2013/058#revision1We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).
Our technical contributions include a theorem that shows that the ``expected shrinkage'' result of Håstad (SIAM J. Comput., 1998) actually holds with very high probability (where the restrictions are chosen from a certain distribution that takes into account the structure of the formula), combining ideas of both Impagliazzo, Meka and Zuckerman (FOCS, 2012) and Komargodski and Raz. In addition, using a bit-fixing extractor in the construction of $h$ allows us to simplify a major part of the analysis of Komargodski and Raz.Sat, 06 Apr 2013 00:03:23 +0300https://eccc.weizmann.ac.il/report/2013/058#revision1
Paper TR13-058
| Improved Average-Case Lower Bounds for DeMorgan Formula Size |
Ilan Komargodski,
Ran Raz,
Avishay Tal
https://eccc.weizmann.ac.il/report/2013/058We give a function $h:\{0,1\}^n\to\{0,1\}$ such that every deMorgan formula of size $n^{3-o(1)}/r^2$ agrees with $h$ on at most a fraction of $\frac{1}{2}+2^{-\Omega(r)}$ of the inputs. This improves the previous average-case lower bound of Komargodski and Raz (STOC, 2013).
Our technical contributions include a theorem that shows that the ``expected shrinkage'' result of Hästad (SIAM J. Comput., 1998) actually holds with very high probability (where the restrictions are chosen from a certain distribution that takes into account the structure of the formula), combining ideas of both Impagliazzo, Meka and Zuckerman (FOCS, 2012) and Komargodski and Raz. In addition, using a bit-fixing extractor in the construction of $h$ allows us to simplify a major part of the analysis of Komargodski and Raz.Fri, 05 Apr 2013 23:32:15 +0300https://eccc.weizmann.ac.il/report/2013/058