# Switching lemma

$\exp\left(\Omega\left(n^{\frac{1}{k-1}}\right)\right)$
The switching lemma says that depth-2 circuits in which some fraction of the variables have been set randomly depend with high probability only on very few variables after the restriction. The name of the switching lemma stems from the following observation: Take an arbitrary formula in conjunctive normal form, which is in particular a depth-2 circuit. Now the switching lemma guarantees that after setting some variables randomly, we end up with a Boolean function that depends only on few variables, i.e., it can be computed by a decision tree of some small depth $d$. This allows us to write the restricted function as a small formula in disjunctive normal form. A formula in conjunctive normal form hit by a random restriction of the variables can therefore be "switched" to a small formula in disjunctive normal form.