On Negations in Boolean Networks

DOI10.1007/978-3-642-03456-5_2zbMath1257.94039OpenAlexW2125793194MaRDI QIDQ3644711

Norbert Blum

Publication date: 12 November 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03456-5_2

zbMATH Keywords

Boolean functionnetwork complexitymonotone networknonmonotone network

Mathematics Subject Classification ID

Related Items (3)

Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A Boolean function requiring 3n network size
• A 4n-lower bound on the monotone network complexity of a one-output Boolean function
• An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
• Lower bounds on monotone complexity of the logical permanent
• The monotone circuit complexity of Boolean functions
• Some remarks on Boolean sums
• Switching functions whose monotone complexity is nearly quadratic
• A new lower bound on the monotone network complexity of Boolean sums
• On another Boolean matrix
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• Complexity of monotone networks for Boolean matrix product
• Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
• Monotone switching circuits and Boolean matrix product
• Graph-theoretic properties in computational complexity
• Symmetric approximation arguments for monotone lower bounds without sunflowers
• On the bottleneck counting argument
• The gap between monotone and non-monotone circuit complexity is exponential
• Higher lower bounds on monotone size
• On the Inversion Complexity of a System of Functions
• A $4n$ Lower Bound on the Combinational Complexity of Certain Symmetric Boolean Functions over the Basis of Unate Dyadic Boolean Functions
• An n3/2 lower bound on the monotone network complexity of the Boolean convolution
• The Complexity of Monotone Networks for Certain Bilinear Forms, Routing Problems, Sorting, and Merging
• The Power of Negative Thinking in Multiplying Boolean Matrices
• Shifting Graphs and Their Applications
• A $2.5n$-Lower Bound on the Combinational Complexity of Boolean Functions
• On the combinational complexity of certain symmetric Boolean functions
• On the Complexity of Negation-Limited Boolean Networks
• The Potential of the Approximation Method
• Negation is Powerless for Boolean Slice Functions
• On Graphs that do not Contain a Thomsen Graph
• A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates
• Natural proofs
• Combinatorics of monotone computations

This page was built for publication: On Negations in Boolean Networks