Stasys Jukna

We prove a general combinatorial lower bound on the

size of monotone circuits. The argument is different from

Razborov's method of approximation, and is based on Sipser's

notion of `finite limit' and Haken's `counting bottlenecks' idea.

We then apply this criterion to the ...
more >>>

Stasys Jukna

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 ...
more >>>