We consider a general model of monotone circuits, which
we call d-local. In these circuits we allow as gates:
(i) arbitrary monotone Boolean functions whose minterms or
maxterms (or both) have length at most <i>d</i>, and
(ii) arbitrary real-valued non-decreasing functions on at
most <i>d</i> variables.
Our main result is a general combinatorial lower bounds criterion
for such circuits. This resolves a problem, raised by Razborov
in 1986, and yields, in a uniform and easy way, non-trivial
lower bounds for circuits computing explicit functions even
for groving <i>d</i>. The proof of the criterion is relatively
simple and direct, and combines the bottlenecks counting method
of Haken with the idea of finite limit due to Sipser.

We demonstrate the criterion by super-polynomial
lower bounds for explicit Boolean functions, associated with
bipartite Paley graphs and partial t-designs. We then derive
exponential lower bounds for clique-like graph functions of
Tardos. This last result together with an observation made by
Rosenbloom (1997) implies that (unlike in the Boolean case)
the power of monotone real and non-monotone Boolean circuits
is <i>incomparable</i>. Since we allow real gates, the criterion
also implies corresponding lower bounds for the length of cutting
planes proof in the propositional calculus.

This is a revised and essentially improved version of ECCC Report TR96--026.