Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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
Downloads: 2797


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]


TR96-026 | 25th March 1996 00:00

Finite Limits and Monotone Computations

Authors: Stasys Jukna
Publication: 25th March 1996 15:05
Downloads: 1583


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 #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
Downloads: 1291


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

ISSN 1433-8092 | Imprint