BPP ⊆ P/poly

Inclusion · Adl78, BG81

Statement

BPP $\subseteq$ poly: every language in $\mathbf{BPP}$ is decided by a family of polynomial-size Boolean circuits. Adl78 proves the $\mathbf{RP}$ case; BG81 extend it to $\mathbf{BPP}$ by the same argument with a majority vote.

Sketch

Amplify the error below $2^{-n}$ by a majority vote over independent runs; a union bound over the $2^n$ inputs of length $n$ shows some random string is correct on all of them, and hardwiring it as advice gives the circuit family.