Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

TR20-102 | 9th July 2020
Stasys Jukna

Notes on Hazard-Free Circuits

Revisions: 2

The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s and is an important problem in circuit design. Recently, Ikenmeyer et al. [J. ACM, 66:4 (2019), Article 25] have shown that the hazard-free circuit complexity of any Boolean function $f(x)$ is lower-bounded by the ... more >>>

ISSN 1433-8092 | Imprint