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.