Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR20-186 | 26th December 2020 23:05

#### Shrinkage of Decision Lists and DNF Formulas

Revision #1
Authors: Benjamin Rossman
Accepted on: 26th December 2020 23:05
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
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).