Combinatorics of monotone computations

Our main result is a combinatorial lower bounds criterion for a general mod el of monotone circuits, where we allow as gates: (i) arbitrary monotone Bo olean functions whose minterms or maxterms (or both) have length less than or equal to d, and (ii) arbitrary real-valued non-decreasing functions on l ess than or equal to d variables. This resolves a problem, raised by Razbor ov in 1986, and yields, in a uniform and easy way, non-trivial lower bounds for circuits computing explicit functions even when d --> infinity. The pr oof 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-des igns. We then derive exponential lower bounds for clique-like graph functio ns of Tardos, thus establishing an exponential gap between the monotone rea l and non-monotone Boolean circuit complexities. Since we allow real gates, the criterion also implies corresponding lower bounds for the length of cu tting planes proof in the propositional calculus.