= Razborov approximation method
{c}
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>.<Razborov's Method of Approximations by Timothy Gowers>[sections 2–4]{ref}
Back to article page
