Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > CLIQUE FUNCTION:
Reports tagged with clique function:
TR96-026 | 25th March 1996
Stasys Jukna

Finite Limits and Monotone Computations

Revisions: 1 , Comments: 1

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 ... more >>>




ISSN 1433-8092 | Imprint