ECCC-Report TR96-026https://eccc.weizmann.ac.il/report/1996/026Comments and Revisions published for TR96-026en-usTue, 04 Jun 1996 00:00:00 +0300
Revision 1
| Finite Limits and Monotone Computations over the Reals Revision of: TR96-026 |
S. Jukna
https://eccc.weizmann.ac.il/report/1996/026#revision1Our 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]
Tue, 04 Jun 1996 00:00:00 +0300https://eccc.weizmann.ac.il/report/1996/026#revision1
Comment 1
| Correction of Theorem 3.1 Comment on: TR96-026 |
Stasys Jukna
https://eccc.weizmann.ac.il/report/1996/026#comment1We 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}$).
Tue, 09 Apr 1996 12:52:10 +0300https://eccc.weizmann.ac.il/report/1996/026#comment1
Paper TR96-026
| Finite Limits and Monotone Computations |
Stasys Jukna
https://eccc.weizmann.ac.il/report/1996/026We 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.
Mon, 25 Mar 1996 15:05:20 +0300https://eccc.weizmann.ac.il/report/1996/026