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}\mathsf{/}\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}$, proving super-polynomial circuit lower bounds for $\mathsf{N}\mathsf{P}$ problems offers a combinatorial route toward separating $\mathsf{P}$ from $\mathsf{N}\mathsf{P}$, formalized by the Karp-Lipton theorem ($\mathsf{N}\mathsf{P}\subseteq \mathsf{P}\mathsf{/}\mathsf{p}\mathsf{o}\mathsf{l}\mathsf{y}⟹\mathsf{P}\mathsf{H}={\mathrm{\Sigma }}_2^p$). While general circuit lower bounds for explicit functions in $\mathsf{N}\mathsf{P}$ remain linear, exponential lower bounds hold for bounded-depth circuits via random restrictions and polynomial approximations. We give a self-contained treatment of both paradigms and their consequences. First, we establish Shannon’s counting lower bound, Lupanov’s $(1+o(1))2^n\mathrm{/}n$ synthesis upper bound, and the Karp-Lipton theorem via SAT self-reducibility. Second, we prove H{\aa}stad’s Switching Lemma via Razborov’s canonical decision-tree encoding, showing that a $k$-CNF or $k$-DNF under a $p$-random restriction collapses to decision-tree depth less than $s$ except with probability at most $(5pk{)}^s$, and derive the optimal $2^{\mathrm{\Omega }(n^{1\mathrm{/}(d-1)})}$ lower bound (and matching $O(n{2}^{n^{1\mathrm{/}(d-1)}})$ upper bound) for Parity in depth-$d$ ${\mathsf{A}\mathsf{C}}^0$. Third, we present the Razborov-Smolensky method over ${\mathbb{F}}_p$, proving that ${\mathrm{M}\mathrm{O}\mathrm{D}}_q\mathrm{\notin }{\mathsf{A}\mathsf{C}}^0[p]$ for distinct primes $p\mathrm{\ne }q$ and establishing a $2^{\mathrm{\Omega }(n^{1\mathrm{/}(2d)})}$ lower bound for Parity against ${\mathsf{A}\mathsf{C}}^0[3]$. Finally, we examine structured restrictions for $k$-Clique and average-case depth hierarchies, four consequences of the Switching Lemma – oracle separations of $\mathsf{P}\mathsf{H}$ from $\mathsf{P}\mathsf{S}\mathsf{P}\mathsf{A}\mathsf{C}\mathsf{E}$, Linial-Mansour-Nisan Fourier concentration, Nisan-Wigderson pseudorandom generators, and ${\mathsf{A}\mathsf{C}}^0$-SAT algorithms – and the Razborov-Rudich Natural Proofs barrier.