Finite limits and monotone computations: the lower bounds criterion
Stasys P. Jukna · 2002
Our main result is a combinatorial lower bounds criterion for monotone circuits over the reals. We allow any 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/sub s//sup m/(x/sub 1/,...,x/sub 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.