论文标题
决策清单和DNF公式的收缩
Shrinkage of Decision Lists and DNF Formulas
论文作者
论文摘要
我们基于$ p $ -random限制$ \ mathbf r_p $ in [0,1] $的所有值，在$ p $ -random限制$ \ mathbf r_p $下建立了几乎紧密的界限。对于带有域$ \ {0,1 \}^n $的函数$ f $，令$ \ mathrm {dl}（f）$表示计算$ f $的决策列表的最小大小。我们证明\ [ \ Mathbb e [\ \ Mathrm {dl}（f {\ upharpoonRight} \ Mathbf r_p）\] \ le \ mathrm {dl}（f）^{\ log_ {2/（1-p）}（\ frac {1+p} {1-p} {1-p}）}。例如，当$ p = \ sqrt {5} -2 \大约0.24 $时，此键为$ \ sqrt {\ mathrm {dl}（f）} $。对于布尔函数$ f $，我们获得了相同的收缩，相对于DNF公式尺寸加$ 1 $（即，用$ \ mathrm {dnf}（\ cdot）（\ cdot）（\ cdot）+1 $替换$ \ mathrm {dl}（\ cdot）$。
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).
