Past exam of the mathematics course of the University of Cambridge / 2023 / iii / Paper 124 / 1 / ii / 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, thenThe 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.