Separating Circuits: Switching Lemmas and Random Restrictions

Non-uniform circuit complexity classifies Boolean functions by the size and depth of the gate networks required to compute them. Because $\mathsf{P} \subseteq \mathsf{P/poly}$, proving super-polynomial circuit lower bounds for $\mathsf{NP}$ problems offers a combinatorial route toward separating $\m