__
Revision #1 to TR20-186 | 26th December 2020 23:05
__
#### Shrinkage of Decision Lists and DNF Formulas

**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

__
TR20-186 | 9th December 2020 17:56
__

#### Shrinkage of Decision Lists and DNF Formulas

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