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]
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.
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}$).
