Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > MONOTONE CIRCUIT:
Reports tagged with monotone circuit:
TR97-032 | 11th July 1997
Jan Johannsen

#### Lower Bounds for Monotone Real Circuit Depth and Formula Size and Tree-like Cutting Planes

Using a notion of real communication complexity recently
introduced by J. Krajicek, we prove a lower bound on the depth of
monotone real circuits and the size of monotone real formulas for
st-connectivity. This implies a super-polynomial speed-up of dag-like
over tree-like Cutting Planes proofs.

more >>>

TR17-048 | 14th March 2017
Pavel Hrubes, Pavel Pudlak

#### A note on monotone real circuits

We show that if a Boolean function $f:\{0,1\}^n\to \{0,1\}$ can be computed by a monotone real circuit of size $s$ using $k$-ary monotone gates then $f$ can be computed by a monotone real circuit of size $O(sn^{k-2})$ which uses unary or binary monotone gates only. This partially solves an open ... more >>>

TR18-154 | 7th September 2018
Stasys Jukna, Andrzej Lingas

#### Lower Bounds for Circuits of Bounded Negation Width

We consider Boolean circuits over $\{\lor,\land,\neg\}$ with negations applied only to input variables. To measure the amount of negation'' in such circuits, we introduce the concept of their negation width.'' In particular, a circuit computing a monotone Boolean function $f(x_1,\ldots,x_n)$ has negation width $w$ if no nonzero term produced (purely ... more >>>

ISSN 1433-8092 | Imprint