Combinatorics of Monotone Computations

Stasys Jukna

Abstract

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 d, and (ii) arbitrary real-valued non-decreasing functions on at most d 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 d. The proof 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 incomparable. Since we allow real gates, the criterion also implies corresponding lower bounds for the length of cutting planes proof in the propositional calculus.

Back to my home page