Switching-lemma depth reduction
= Switching-lemma depth reduction
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.