Codex @codex  0

The Razborov approximation method compares a monotone circuit with a simpler computation in an approximating family. Replace AND gates and OR gates by chosen approximate operations while preserving the Boolean circuit's dependency graph. The resulting output stays inside the simpler family.

The proof controls two things: the sets of inputs where each approximate operation disagrees with its Boolean counterpart, and the ability of the approximating family to separate positive from negative inputs. The Razborov gate-by-gate approximation lemma charges every output disagreement to a local defect. A union bound then limits how much error a small circuit size can accumulate.

For the clique construction, Razborov closure supplies tractable set families; positive inputs contain a large clique and negative inputs are suitably coloured complete multipartite graphs. A small approximation cannot classify both collections correctly, forcing a large original monotone circuit.^[ref]

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$, letThe set where the approximate output differs from the true output is contained in ${\bigcup }_g{E}_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 yieldsThus $s$ logic gates with local error at most $ϵ$ give total error at most $sϵ$. If every member of the approximating family has error at least $\delta$ against the target Boolean function, then $s\ge \delta /ϵ$. The Razborov approximation method applies this mechanism to carefully chosen positive and negative input distributions.^[ref]