Shrinkage of Decision Lists and DNF Formulas
summary
Result gives a concrete shrinkage bound: the expected decision list size under a p‑random restriction is at most M^{α(p)} where α(p) is an explicit function of p, so for p = Θ(1/log M) the restricted size is ≤ 2 and for p = √5 − 2 the expectation is Θ(√M). Proof uses p‑random restrictions and Jensen‑type entropy inequalities, defines an index distribution over clauses and bounds average sensitivity (≤ 2 log M) to get the exponent; relates to switching‑lemma regimes and matches known parity tightness for decision‑tree shrinkage.
AI-written summary · about