Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR96-026 | 4th June 1996 00:00

#### Finite Limits and Monotone Computations over the Reals Revision of: TR96-026

Revision #1
Authors: S. Jukna
Accepted on: 4th June 1996 00:00
Keywords:

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

TR96-026
Authors: Stasys Jukna
Publication: 25th March 1996 15:05
Keywords:

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

Comment #1
Authors: Stasys Jukna
Accepted on: 9th April 1996 12:52
Keywords:

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

ISSN 1433-8092 | Imprint