Monotone circuit complexity

Monotone circuit complexity studies Boolean circuits built only from AND and OR gates, without negations. Such circuits compute monotone Boolean functions, but some monotone functions require much larger monotone circuits than unrestricted circuits.

The Razborov approximation method replaces the AND and OR operations of a monotone circuit by tractable lattice operations. If each gate introduces only a controlled set of positive or negative errors, a small circuit cannot separate all positive inputs from all negative inputs.

Fix integers $r$ and $l$. The Razborov closure of a family of vertex sets of size at most $l$ repeatedly adjoins a set $W$ whenever there are $r$ existing sets $W_1,\dots ,W_r$ whose pairwise intersections are contained in $W$. A family equal to its closure is called $r$-closed.

An $r$-closed family has at most $(r-1{)}^k$ inclusion-minimal members of cardinality $k$. This limits the number of cliques accepted by a proper closed approximation.

The Razborov gate-by-gate approximation lemma compares a monotone circuit with the lattice computation obtained by replacing each gate by an approximate meet or join. Every disagreement at the output is charged to an error introduced by one of the circuit's gates.