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{\upharpoonright}\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).