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 #1 to TR20-186 | 26th December 2020 23:05

Shrinkage of Decision Lists and DNF Formulas

RSS-Feed




Revision #1
Authors: Benjamin Rossman
Accepted on: 26th December 2020 23:05
Downloads: 28
Keywords: 


Abstract:

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



Changes to previous version:

Corrected a typo in Proposition 12


Paper:

TR20-186 | 9th December 2020 17:56

Shrinkage of Decision Lists and DNF Formulas





TR20-186
Authors: Benjamin Rossman
Publication: 13th December 2020 09:19
Downloads: 104
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint