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.

A monotone Boolean circuit uses only AND and OR gates, variables, and optional constants. It computes a monotone Boolean function; negation gates are excluded.

In the finite lattice approximation for monotone clique circuits, set $m=r=\lfloor n^{1/4}\rfloor$ and $\ell =\lfloor {\log }_{2}n\rfloor$. A nonuniversal output accepts at most ${\sum }_{s=2}^{\ell }s!(r-1{)}^s(m/n{)}^s\le 2(\ell rm/n{)}^2$ of uniform positive cliques. Its missing positives require the circuit size times the positive clique error of a truncated lattice meet to be bounded below. A universal output accepts every negative colouring input; those errors require the circuit size times the negative colouring error of a forced-set closure to be at least one. Both alternatives imply the displayed superpolynomial bound by the Razborov gate-by-gate approximation lemma.

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.

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 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 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.

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.