Reductions for monotone Boolean circuits
type: Item
instance of: scholarly article
title: Reductions for monotone Boolean circuits
zbMATH Open document ID: 1151.94014
author: Kazuo Iwama
author: Hiroki Morizumi
author: Jun Tarui
published in: Theoretical Computer Science
publication date: 2008-12-12T00:00:00Z
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 5382276
zbMATH Keywords: circuit complexity
zbMATH Keywords: monotone circuit
zbMATH Keywords: negation-limited circuit
zbMATH Keywords: majority function
zbMATH Keywords: merging function
MaRDI profile type: Publication
full work available at URL: j.tcs.2008.08.009
OpenAlex ID: W1996760375
cites work: A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
cites work: On the negation-limited circuit complexity of merging
cites work: Q4726174
cites work: On the Complexity of Negation-Limited Boolean Networks
cites work: Optimal Rearrangeable Multistage Connecting Networks
cites work: Higher lower bounds on monotone size
cites work: Q4708583
cites work: Negation-Limited Complexity of Parity and Inverters
cites work: Explicit lower bound of 4.5n - o(n) for boolena circuits
cites work: The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging
cites work: Q4385520
cites work: Shifting Graphs and Their Applications
cites work: Q3758729
cites work: Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
cites work: Q4503971
cites work: An exponential gap with the removal of one negation gate
cites work: Graph-theoretic properties in computational complexity
cites work: Short monotone formulae for the majority function
cites work: Q3762226
cites work: A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
DOI: 10.1016/J.TCS.2008.08.009
Recommended article: Reductions for Monotone Boolean Circuits
Recommended article: Q3352968
Recommended article: The reduction of general Boolean functions to monotonic form
Recommended article: The monotone circuit complexity of Boolean functions
Recommended article: Boolean reducibility
Recommended article: The monotone circuit complexity of quadratic Boolean functions
Recommended article: Non-cancellative Boolean circuits: A generalization of monotone boolean circuits
Recommended article: On the complexity of monotone circuits for threshold symmetric Boolean functions
Recommended article: Algorithms and Computation
Recommended article: Q5202146
description: scientific article; zbMATH DE number 5382276