Reductions for monotone Boolean circuits

DOI10.1016/j.tcs.2008.08.009zbMath1151.94014OpenAlexW1996760375MaRDI QIDQ959813

Hiroki Morizumi, Jun Tarui, Kazuo Iwama

Publication date: 12 December 2008

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2008.08.009

zbMATH Keywords

circuit complexitymajority functionmonotone circuitnegation-limited circuitmerging function

Mathematics Subject Classification ID

Related Items (1)

Maximal sensitivity of Boolean nested canalizing functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Graph-theoretic properties in computational complexity
• An exponential gap with the removal of one negation gate
• On the negation-limited circuit complexity of merging
• Higher lower bounds on monotone size
• Short monotone formulae for the majority function
• A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging
• Shifting Graphs and Their Applications
• On the Complexity of Negation-Limited Boolean Networks
• Explicit lower bound of 4.5n - o(n) for boolena circuits
• Optimal Rearrangeable Multistage Connecting Networks
• Negation-Limited Complexity of Parity and Inverters
• A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates

This page was built for publication: Reductions for monotone Boolean circuits