Switching_lemma
In computational complexity theory, Håstad's switching lemma is a key tool for proving lower bounds on the size of constant-depth Boolean circuits. It was first introduced by Johan Håstad to prove that AC0 Boolean circuits of depth k require size to compute the parity function on bits.[1] He was later awarded the Gödel Prize for this work in 1994.
The switching lemma describes the behavior of a depth-2 circuit under random restriction, i.e. when randomly fixing most of the coordinates to 0 or 1. Specifically, from the lemma, it follows that a formula in conjunctive normal form (that is, an AND of ORs) becomes a formula in disjunctive normal form (an OR and ANDs) under random restriction, and vice versa. This "switching" gives the lemma its name.