Separating Circuits: Switching Lemmas and Random Restrictions

Abstract

Non-uniform circuit complexity classifies Boolean functions by the size and depth of the gate networks required to compute them. Because $\mathsf{P}\subseteq P/poly$, proving super-polynomial circuit lower bounds for $\mathsf{NP}$ problems offers a combinatorial route toward separating $\mathsf{P}$ from $\mathsf{NP}$, formalized by the Karp-Lipton theorem ($\mathsf{NP}\subseteq P/poly⟹\mathsf{PH}={\Sigma }_2^p$). While general circuit lower bounds for explicit functions in $\mathsf{NP}$ 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/n$ synthesis upper bound, and the Karp-Lipton theorem via SAT self-reducibility. Second, we prove Hå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^{\Omega (n^{1/(d-1)})}$ lower bound (and matching $O(n{2}^{n^{1/(d-1)}})$ upper bound) for Parity in depth-$d$ ${\mathsf{AC}}^0$. Third, we present the Razborov-Smolensky method over ${\mathbb{F}}_p$, proving that ${\mathrm{MOD}}_q\notin {\mathsf{AC}}^0[p]$ for distinct primes $p\ne q$ and establishing a $2^{\Omega (n^{1/(2d)})}$ lower bound for Parity against ${\mathsf{AC}}^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{PH}$ from $\mathsf{PSPACE}$, Linial-Mansour-Nisan Fourier concentration, Nisan-Wigderson pseudorandom generators, and ${\mathsf{AC}}^0$-SAT algorithms -- and the Razborov-Rudich Natural Proofs barrier.