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.