= Razborov gate-by-gate approximation lemma
{c}
Suppose the input nodes of a <Boolean circuit> are represented exactly and each internal <logic gate> is replaced by an approximate operation. For <logic gate> $g$ with children $a,b$, let
$$
E_g=\{x:\widetilde f_g(x)\ne\operatorname{op}_g(\widetilde f_a(x),\widetilde f_b(x))\}.
$$
The <set> where the approximate output differs from the true output is contained in $\bigcup_gE_g$. Indeed, at an <input> outside every $E_g$, induction through the acyclic dependency <graph> proves equality at every <logic gate>. Shared subcircuits are charged once per <logic gate>, rather than once per path.
For any <probability measure> $\mu$, a <union bound> yields
$$
\mu(\widetilde f_{\mathrm{out}}\ne f_{\mathrm{out}})\leq\sum_g\mu(E_g).
$$
Thus $s$ <logic gates> with local error at most $\epsilon$ give total error at most $s\epsilon$. If every member of the approximating family has error at least $\delta$ against the target <Boolean function>, then $s\geq\delta/\epsilon$. The <Razborov approximation method> applies this mechanism to carefully chosen positive and negative input distributions.<Razborov's Method of Approximations by Timothy Gowers>[section 2, gate-by-gate error containment]{ref}
Back to article page
