= Solution
In one standard form, the <Håstad switching lemma> says that if $F$ is a $k$-DNF and $\rho$ is a random restriction that independently leaves each variable unset with probability $p$ and otherwise assigns it a uniform Boolean value, then
$$
\mathbb P_\rho\bigl[D(F\upharpoonright\rho)\geq t\bigr]
\leq(5pk)^t.
$$
The dual statement exchanges DNF and CNF. Thus a small-width DNF becomes, with high probability, a shallow decision tree and hence a small-width CNF after a sufficiently sparse random restriction.
Back to article page
