Monotone Circuits and the Approximation Method

A monotone circuit uses only AND and OR gates, with no negations anywhere, and its inputs are the bits of a graph or a set. Such a circuit computes a monotone function: adding an edge or an element can only turn the output from 0 to 1, never the reverse. Clique is monotone, and so is connectivity, matching, and set cover. Monotone circuit complexity asks how many gates these functions need when the circuit is forbidden from using the one operation that would make the problem easy — and for clique the answer is exponential, proved.

The model, and why dropping NOT changes everything

A monotone circuit over $n$ input bits has gates $\wedge$ and $\vee$ of arbitrary fan-in, constants, and no negated literals. Because there are no negations, every gate’s output is a monotone function of its inputs, so the circuit can only compute a monotone Boolean function.

The restriction is not a technical convenience. Every function in $\mathrm{P}$ has a monotone circuit of polynomial size if negations are allowed; the interesting question is what happens when they are not. And the answer, for several functions, is that the monotone size is exponential even though the unrestricted size is polynomial. Clique is the standard example: the function is in $\mathrm{P}$ (check all $\binom{n}{k}$ candidate vertex sets), has polynomial-size unrestricted circuits, and requires $n^{\Omega(\log n)}$ monotone gates for $k$ around $n^{1/4}$.

That gap is the point of the model. A lower bound in the monotone world is provable, and its proof techniques are informative precisely because they cannot be transferred to the unrestricted world — the transfer would require a way to eliminate negations, and no such way exists.

The approximation method, in outline

Razborov’s approximation method replaces the circuit’s gates with simpler functions one at a time, and tracks how far the replacement drifts from the original. The construction below follows his original argument for the clique function; the constants were later improved by Alon and Boppana, whose version is the one usually quoted.

The setup fixes a target function $f$, here the clique function on $N = \binom{n}{2}$ edges with clique size $k$. The method defines a sequence of approximations, one per gate, each a function that agrees with the gate on most inputs but has a simpler structure. Agreement is measured by a distribution over inputs, and the distribution is chosen adversarially: it should concentrate on inputs where the gate’s value is easy to determine, so that the approximation is accurate where it matters.

The induction is over the circuit. For an AND gate whose children have been replaced by approximations $A_1$ and $A_2$, the replacement is $A_1 \wedge A_2$ or a further simplification of it. The technical content is a lemma showing that each replacement introduces a bounded error: the fraction of inputs on which the new approximation differs from the old gate grows by at most a fixed amount, and the amount is small enough that after all $s$ gates the accumulated error stays below one half.

The contradiction follows. If the circuit computes clique exactly, then after replacing every gate the final approximation computes a function that is within $1/2$ of clique on the chosen distribution, and the approximation has a specific structural form that cannot be that close. The structural form is what the method buys: after $s$ replacements, the output function is a low-degree polynomial threshold or a small union of simple sets, and clique is far from any such object under the distribution.

The distribution, and why it must be adversarial

The choice of distribution is where the method earns its name, and where the exponential bound comes from.

The distribution is supported on sparse random graphs rather than on arbitrary ones. Edge density is chosen low enough that a $k$-clique is very unlikely, yet high enough that small cliques and near-cliques are plentiful, and the analysis counts the sets that occur. Under that distribution, a monotone circuit’s gate values are highly biased — most gates are 0 on most inputs — and an approximation that agrees with a gate on most inputs can be much simpler than the gate itself.

The quantitative step is an entropy or counting estimate on the number of distinct sets that a small monotone formula can describe. A monotone DNF with $s$ terms can describe at most $s$ distinct minimal satisfying sets; a clique function on $k$ vertices has $\binom{n}{k}$ minimal satisfying sets, one per vertex subset. If the approximation preserves the minimal sets up to an error of $1/2$ in the distribution, the number of terms must be at least the number of sets that carry non-negligible probability, which under this distribution is exponential in $k \log n$.

The Alon-Boppana refinement replaced Razborov’s distribution with a cleaner one and improved the constant in the exponent. Their version uses a random graph with edge probability around $n^{-2/(k-1)}$, chosen so that the expected number of $k$-cliques is about one, and the bound becomes $n^{\Omega(k)}$ for $k$ up to $n^{1/4}$. Beyond that range the density choice stops separating the cases, and the method’s exponent degrades.

What the method proves and what it misses

Clique is exponential, and the bound is unconditional. So is the monotone complexity of the set-cover function and of several related problems, by the same approximation scheme.

Matching is not. The perfect matching function — does a graph contain a perfect matching — is monotone, is in $\mathrm{P}$, and has monotone circuits of polynomial size, so no exponential size bound exists to prove. The known monotone lower bounds for matching are depth bounds, not size bounds, and the approximation method’s inability to say anything about size there is a correct reflection of the object rather than a failure of technique.

The deeper limitation is the one that motivates the natural proofs barrier: the approximation method uses a property — closeness to a simple function under a distribution — that is checkable and large, and Razborov showed that any extension of the method to unrestricted circuits would yield a polynomial-time algorithm for factoring, and no such algorithm is known. The monotone results are therefore walled off from the general case by a conditional, not by a gap in ingenuity alone.

Monotone versus unrestricted, in numbers

For the clique function on $n$ vertices with clique size $k$:

• Unrestricted circuit size: polynomial, since the function is in $\mathrm{P}$ and $\mathrm{P} \subseteq \mathrm{P/poly}$.
• Monotone circuit size: $n^{\Omega(k)}$, by Razborov and Alon-Boppana, exponential for $k = n^{1/4}$.
• Monotone formula size: larger still, and the gap between monotone circuits and monotone formulas follows the general formula bound.

The ratio between the first two entries is the measure of what negations buy, and it is unbounded. For clique, the negations are doing real work: the polynomial algorithm enumerates candidate sets and checks them, and the check uses inequality tests that are not monotone in the edge variables.

def has_clique(n, k, edges):
    """edges: set of frozenset({u, v}). Monotone predicate: adding edges
    cannot change True to False. The check below is not a circuit, but it
    shows the polynomial algorithm that a monotone circuit must match."""
    from itertools import combinations
    for cand in combinations(range(n), k):
        if all(frozenset((u, v)) in edges
               for u, v in combinations(cand, 2)):
            return True
    return False

# The predicate is monotone in `edges`, yet no polynomial-size monotone
# circuit computes it: the enumeration is inherently non-monotone because
# rejecting a candidate uses the absence of an edge.

The comment states the intuition that the lower bound formalises: a monotone circuit can only accumulate positive evidence, and rejecting a candidate set requires ruling out every completion of it, which is a negative fact about the input.

Why the model is still worth studying

Three reasons, none of them about clique specifically.

Monotone circuits are the right model for a class of database and network queries where the input is a set of facts and the query asks whether a pattern exists. Query evaluation over a positive relational algebra — select, project, join, union, no negation — is monotone circuit evaluation in a direct encoding: base relations become groups of input bits, joins become conjunctions and unions become disjunctions. The monotone lower bounds therefore translate into limits on how much a positive query can be compressed, and the size-depth tradeoffs apply directly to the parallel evaluation of such queries.

The approximation method is a template. Its structure — replace gates by simpler functions, bound the drift, derive a contradiction from a structural property of the final approximation — recurs in the algebraic and polynomial-method lower bounds, and the Razborov-Smolensky argument is a direct descendant with polynomials in place of sets. Reading the monotone proof first makes the algebraic one legible.

And the separation between monotone and unrestricted complexity is itself a structural fact. It shows that the difficulty of circuit lower bounds is concentrated in the negations, and that any proof for general circuits must handle a resource that the monotone methods deliberately exclude. That observation is the informal content of the natural proofs barrier, and it is why the monotone results, strong as they are, have not produced a single unconditional bound for a function in $\mathrm{NP}$ over a complete basis.