ECCC-Report TR20-186https://eccc.weizmann.ac.il/report/2020/186Comments and Revisions published for TR20-186en-usSat, 26 Dec 2020 23:05:07 +0200
Revision 1
| Shrinkage of Decision Lists and DNF Formulas |
Benjamin Rossman
https://eccc.weizmann.ac.il/report/2020/186#revision1We establish nearly tight bounds on the expected shrinkage of decision lists and DNF formulas under the $p$-random restriction $\mathbf R_p$ for all values of $p \in [0,1]$. For a function $f$ with domain $\{0,1\}^n$, let $\mathrm{DL}(f)$ denote the minimum size of a decision list that computes $f$. We show that
\[
\mathbb E[\ \mathrm{DL}(f|\mathbf R_p)\ ] \le
\mathrm{DL}(f)^{\log_{2/(1-p)}(\frac{1+p}{1-p})}.
\]
For example, this bound is $\sqrt{\mathrm{DL}(f)}$ when $p = \sqrt{5}-2 \approx 0.24$. For Boolean functions $f$, we obtain the same shrinkage bound with respect to DNF formula size plus $1$ (i.e.,\ replacing $\mathrm{DL}(\cdot)$ with $\mathrm{DNF}(\cdot)+1$ on both sides of the inequality).Sat, 26 Dec 2020 23:05:07 +0200https://eccc.weizmann.ac.il/report/2020/186#revision1
Paper TR20-186
| Shrinkage of Decision Lists and DNF Formulas |
Benjamin Rossman
https://eccc.weizmann.ac.il/report/2020/186We establish nearly tight bounds on the expected shrinkage of decision lists and DNF formulas under the $p$-random restriction $\mathbf R_p$ for all values of $p \in [0,1]$. For a function $f$ with domain $\{0,1\}^n$, let $\mathrm{DL}(f)$ denote the minimum size of a decision list that computes $f$. We show that
\[
\mathbb E[\ \mathrm{DL}(f|\mathbf R_p)\ ] \le
\mathrm{DL}(f)^{\log_{2/(1-p)}(\frac{1+p}{1-p})}.
\]
For example, this bound is $\sqrt{\mathrm{DL}(f)}$ when $p = \sqrt{5}-2 \approx 0.24$. For Boolean functions $f$, we obtain the same shrinkage bound with respect to DNF formula size plus $1$ (i.e.,\ replacing $\mathrm{DL}(\cdot)$ with $\mathrm{DNF}(\cdot)+1$ on both sides of the inequality).Sun, 13 Dec 2020 09:19:56 +0200https://eccc.weizmann.ac.il/report/2020/186