Stasys Jukna
Abstract
Our main result is a combinatorial lower bounds criterion for
monotone circuits over the reals. We allow any {\em unbounded}
fanin non-decreasing real-valued functions as gates.
The only requirement is their "locality". Unbounded fanin AND and OR
gates, as well as any threshold gate $T_s^m(x_1,\ldots,x_m)$ with
small enough threshold value $\min\{s, m-s+1\}$, are simplest examples of
local gates. The proof is relatively simple and direct, and
combines the bottlenecks counting approach of Haken with the idea of
finite limit due to Sipser. Apparently this is the first
combinatorial lower bounds criterion for monotone computations. It
is symmetric and yields (in a uniform and easy way) exponential
lower bounds.
REMARK: First symmetric lower bounds criterion for circuits with fanin-2
AND/OR gates was obtained in
S. Jukna, A criterion for monotone
circuit complexity (1991, unpublished manuscript)
There such criterion was derived using Razborov's method of
approximations. Interestingly enough, the criterion is allmost the
same as we get in the present paper using Haken's approach.
Back to my home page