 Håstad switching lemma

The Håstad switching lemma says that a small-width DNF or CNF becomes representable by a shallow decision tree with high probability under a sufficiently sparse random restriction. Iterating it is a central method for proving lower bounds against constant-depth circuits.