Jukna, Stasys Combinatorics of monotone computations. (English) Zbl 0962.03030 Combinatorica 19, No. 1, 65-85 (1999). Summary: Our main result is a combinatorial lower bound criterion for a general model of monotone circuits, where we allow as gates: (i) arbitrary monotone Boolean functions whose minterms or maxterms (or both) have length \(\leq d\), and (ii) arbitrary real-valued non-decreasing functions on \(\leq d\) variables. This resolves a problem, raised by A. A. Razborov [in: Proc. Int. Congr. Math. (Berkeley, 1986), 1478-1487 (1987; Zbl 0668.94020)], and yields, in a uniform and easy way, non-trivial lower bounds for circuits computing explicit functions even when \(d\to \infty\). The proof is relatively simple and direct, and combines the bottlenecks counting method of A. Haken [in: 36th Annual Symp. on Foundations of Computer Science, IEEE Computer Soc. Press, 36-40 (1995; Zbl 0938.68660)] with the idea of finite limit due to M. Sipser [in: Theory of algorithms, Coll. Math. Soc. János Bolyai 44, 387-391 (1986; Zbl 0618.03017)].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, thus establishing an exponential gap between the monotone real and non-monotone Boolean circuit complexities. Since we allow real gates, the criterion also implies corresponding lower bounds for the length of cutting planes proof in the propositional calculus. Cited in 7 Documents MSC: 03D15 Complexity of computation (including implicit computational complexity) 68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) 05D15 Transversal (matching) theory 68R05 Combinatorics in computer science 03F07 Structure of proofs 03B05 Classical propositional logic 68Q05 Models of computation (Turing machines, etc.) (MSC2010) Keywords:monotone computations; monotone circuits; super-polynomial lower bounds; Boolean functions; bipartite Paley graphs; partial \(t\)-designs; exponential lower bounds; clique-like graph functions; cutting planes proof Citations:Zbl 0668.94020; Zbl 0938.68660; Zbl 0618.03017 PDFBibTeX XMLCite \textit{S. Jukna}, Combinatorica 19, No. 1, 65--85 (1999; Zbl 0962.03030) Full Text: DOI