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]

Take upward-closed set families of subsets of $[n]$ of size at most $\ell$, closed under the forcing rule in Razborov closure. Normalize any family containing a set of size at most one to the full family, since its clique predicate is identically true. Intersection is the meet in a lattice; closure of the union is the join in a lattice. A family represents the graphs containing a clique on at least one of its members. The approximate meet can lose positive inputs and the approximate join can acquire negative inputs. The Razborov gate-by-gate approximation lemma charges output errors to those local errors.

Independently colour each vertex with one of $m-1$ colours and join differently coloured vertices. This complete multipartite graph has no $m$-clique. If a forced set $W$ is rainbow but its $r$ witnesses are not, condition on the colours of $W$. The disjoint petals make those failure events conditionally independent. For each witness of size at most $\ell$, the probability of a colour collision is at most $\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)/(m-1)$. If this is at most $1/2$, one closure step causes an error with probability at most $2^{-r}$. There are at most $n^{\ell +1}$ possible steps; apply the union bound.

Choose a uniform $m$-subset $Z$ and the graph consisting only of its clique. Acceptance by two approximating set families but rejection by their intersection requires two minimal witnesses whose union has size greater than $\ell$. At least one has size greater than $\ell /2$. The sunflower bound for minimal members of a Razborov-closed family and $\mathbb{P}(W\subseteq Z)\le (m/n{)}^{|W|}$ give $2{\sum }_{s>\ell /2}s!(r-1{)}^s(m/n{)}^s\le 4q^{\ell /2}$.

Fix a finite ground set $V$, an integer $r\ge 2$ and a size limit $\ell$. The Razborov closure of a set family $\mathcal{F}\subseteq \{A\subseteq V:|A|\le \ell \}$ repeatedly adjoins a set $W$ of size at most $\ell$ whenever existing members $W_1,\dots ,W_r$ satisfyAll adjoined sets remain in the same truncated ambient family. The process terminates because that family is finite. The final family is the least family containing $\mathcal{F}$ that is closed under the rule, so the result does not depend on the order of additions.

For $r=2$, the members $\{1,2\}$ and $\{1,3\}$ force $\{1\}$. In the finite lattice approximation for monotone clique circuits, this rule supplies a closure operation used to form approximate joins. It can add a smaller witness, which is why closure constrains the number of inclusion-minimal members.^[ref]

An inclusion-minimal $s$-set in an upward-closed family cannot belong to an $r$-member delta-system of such minimal sets: its proper core would be adjoined by Razborov closure, violating minimality. The Erdős–Rado sunflower lemma therefore bounds the number $a_s$ of minimal $s$-sets. This weaker factorial bound is sufficient for the superpolynomial monotone clique lower bound.

For $r\ge 2$, an $r$-closed set family has at most $(r-1{)}^k$ inclusion-minimal members of size $k$. This is stronger than the factorial estimate obtained from the Erdős–Rado sunflower lemma alone.

Here is the induction on $r$. For $r=2$, two distinct minimal members force their proper intersection, a contradiction, so at most one minimal member exists. For $r>2$, choose a minimal $k$-set $Z$ and group the minimal members $X$ by $W=X\cap Z$. The remainder $X\setminus Z$ is minimal in the family of sets $B$ outside $Z$ for which $B\cup W$ belongs to the original family.

That remainder family is $(r-1)$-closed: adding $Z$ as the final witness turns each $(r-1)$-witness forcing step into an original $r$-witness step. Induction bounds the group for $W$ by $(r-2{)}^{k-|W|}$; the group $W=Z$ contains only $Z$. Therefore the binomial theorem givesThe case $k=0$ has at most the single empty set. The forcing argument explains why the stronger bound uses the full closure rule rather than only a sunflower prohibition.^[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]