### Revision(s):

__
Revision #1 to TR96-026 | 4th June 1996 00:00
__
#### Finite Limits and Monotone Computations over the Reals Revision of: TR96-026

**Abstract:**
Our main result is a general and easy to apply combinatorial

lower bounds criterion for:

(a) circuits with unbounded fan-in AND and OR gates, and

(b) circuits with arbitrary non-decreasing real functions

of large fan-in as gates.

The combinatorial part of our argument is very simple.

It combains the "bottlenecks counting" idea of Haken with the

notion of "finite limit" due to Sipser.

[This is a revised and extended version of ECCC TR96-026]

### Paper:

__
TR96-026 | 25th March 1996 00:00
__

#### Finite Limits and Monotone Computations

**Abstract:**
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 CLIQUE function on $n$

variables and obtain an $\exp(\Omega(n^{1/4}))$ lower bound for it.

This almost matches the trivial upper bound, which is exponential in

$O(n^{1/4}\log n),$ and improves the best previous lower bound

$\exp(\Omega((n^{1/6}/(\log n)^{1/3}))$ obtained by Alon and Boppana

using the method of approximations. Moreover, our bound holds for

circuits with {\em unbounded} fan-in AND, OR gates and {\em any}

monotone Boolean functions of fan-in at most $n^{1/4}$ at the bottom,

supplementing a result due to Yao that CLIQUE has no polynomial size

monotone circuit with fan-in $n^{\epsilon}$ monotone gates.

Main result, however, is the transparency of the whole argument: the

combinatorial part is very simple, essentially trivial.

### Comment(s):

__
Comment #1 to TR96-026 | 9th April 1996 12:52
__
#### Correction of Theorem 3.1 Comment on: TR96-026

**Abstract:**
We correct one numerical error in the proof of Theorem 3.1.

Specifically, the upper bound on the s-th degree of X^0

is $(k-1)^{m-s/2}$ (rather than $(k-2)^{m-s}$). The

consequence of this correction is that

the lower bound for CLIQUE given by Theorem 3.1, is

exponential in $\Omega(n^{1/6})$ (rather than in

$\Omega(n^{1/4}$).