Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #2 to TR13-058 | 14th May 2017 08:58

#### Improved Average-Case Lower Bounds for De Morgan Formula Size

Revision #2
Authors: Ilan Komargodski, Ran Raz, Avishay Tal
Accepted on: 14th May 2017 08:58
Keywords:

Abstract:

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

Changes to previous version:

Fixed several typos, fixed a bug from the previous version that appeared in Appendix A (and moved the relevant proof to Section 4), and
improved the formula size lower bounds by using the tight shrinkage result from [Tal14].

Revision #1 to TR13-058 | 6th April 2013 00:03

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

Revision #1
Authors: Ilan Komargodski, Ran Raz, Avishay Tal
Accepted on: 6th April 2013 00:03
Keywords:

Abstract:

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

Changes to previous version:

Fixed a typo in the abstract.

### Paper:

TR13-058 | 5th April 2013 23:28

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

TR13-058
Authors: Ilan Komargodski, Ran Raz, Avishay Tal
Publication: 5th April 2013 23:32
We 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.