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.

Switching-lemma depth reduction applies the Håstad switching lemma to every bottom-layer gate, replaces each restricted gate by a shallow decision tree, and merges adjacent layers of the same gate type. Repetition reduces a constant-depth circuit to a bounded-depth decision tree while retaining many live variables.