Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Boolean circuit:
TR07-045 | 24th April 2007
Heribert Vollmer

The complexity of deciding if a Boolean function can be computed by circuits over a restricted basis

We study the complexity of the following algorithmic problem: Given a Boolean function $f$ and a finite set of Boolean functions $B$, decide if there is a circuit with basis $B$ that computes $f$. We show that if both $f$ and all functions in $B$ are given by their truth-table, ... more >>>

TR14-184 | 29th December 2014
Ruiwen Chen, Valentine Kabanets

Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits

We revisit the gate elimination method, generalize it to prove correlation bounds of boolean circuits with Parity, and also derive deterministic #SAT algorithms for small linear-size circuits. In particular, we prove that, for boolean circuits of size $3n - n^{0.51}$, the correlation with Parity is at most $2^{-n^{\Omega(1)}}$, and there ... more >>>

TR18-108 | 1st June 2018
Andrzej Lingas

Small Normalized Boolean Circuits for Semi-disjoint Bilinear Forms Require Logarithmic Conjunction-depth

We consider normalized Boolean circuits that use binary operations of disjunction and conjunction, and unary negation, with the restriction that negation can be only applied to input variables. We derive a lower bound trade-off between the size of normalized Boolean circuits computing Boolean semi-disjoint bilinear forms and their conjunction-depth (i.e., ... 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