 Razborov approximation method

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]