Computer science Randomized, circuit, counting and interactive complexity Theorem

Razborov's monotone circuit lower bound

Builds on Boolean circuit Circuit complexity Clique

Statement

A monotone circuit is a Boolean circuit whose gates are AND and OR gates of fan-in two, with no NOT gates. Let $n \ge 2$ and $2 \le k \le n$ . Take one variable $x_{\set{u,v}}$ for each pair of vertices $u \ne v$ in $\set{1, \ldots, n}$ . An assignment of these variables describes the graph with edge set $\set{\set{u,v} : x_{\set{u,v}} = 1}$ . Let $\mathrm{CLIQUE}_{k,n}$ be the Boolean function that is $1$ exactly when this graph contains a clique with $k$ vertices. Then there is a constant $\varepsilon > 0$ with the following property. For all $n$ and all $k$ with $2 \le k \le n^{1/4}$ , every monotone circuit for $\mathrm{CLIQUE}_{k,n}$ has at least $2^{\varepsilon \sqrt{k}}$ gates.

Remarks

Alexander Razborov proved in 1985 the first superpolynomial lower bound for monotone circuits computing clique functions, and Alon and Boppana sharpened it to the exponential form above. For $k = \floor{n^{1/4}}$ the bound is $2^{\varepsilon n^{1/8}}$ , which is superpolynomial in the number of variables. The proof is the method of approximations: each gate is replaced by an approximator, a small OR of "clique indicators", and the sunflower lemma keeps the approximators small. Each replacement makes few errors on two test distributions, graphs consisting of one $k$ -clique and complete $(k-1)$ -partite graphs, but the final approximator must err on many of them.

The hypothesis of monotonicity is essential to the method. Razborov also showed that perfect matching in bipartite graphs, which is in P, requires monotone circuits of size $n^{\Omega(\log n)}$ . So monotone circuit size can be much larger than general circuit size, and the result does not imply a lower bound for general circuits.

Going deeper

For a student

Clique detection is a monotone function: adding edges never destroys a clique. So it has monotone circuits, and monotone circuit size is a natural first target for lower bounds. The approximation method and the sunflower lemma became standard tools of circuit complexity. Later, Tardos gave a monotone function in P that needs exponential-size monotone circuits, which shows that the gap between monotone and general circuits can be exponential.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Boolean circuit concept
Circuit complexity concept
Clique concept
Razborov's monotone circuit lower bound statement

Tag	`2XH5VDJ426`
URI	`m2://2XH5VDJ426`
Kind	statement, theorem
Writing	W0 stub
MSC	68Q17, 68Q06, 05C69
Status	This copy of the site has no build data. Run `m2 status 2XH5VDJ426`.
About	Circuit complexity
Uses	Boolean circuit, Circuit complexity, Clique
Changed	3 November 2026