Boolean functions whose monotone complexity is of size \(n^ 2\) / log n

DOI10.1016/0304-3975(89)90084-4zbMath0488.94035OpenAlexW4230950430MaRDI QIDQ1166489

Ingo Wegener

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0304-3975(89)90084-4

zbMATH Keywords

sequence of monotone Boolean functions

Mathematics Subject Classification ID

Related Items (11)

More on the complexity of slice functions ⋮ The complexity of central slice functions ⋮ The monotone circuit complexity of Boolean functions ⋮ Entropy of contact circuits and lower bounds on their complexity ⋮ On monotone simulations on nonmonotone networks ⋮ Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution ⋮ Constructive universal algebra: An introduction ⋮ On Negations in Boolean Networks ⋮ Relating monotone formula size and monotone depth of Boolean functions ⋮ On the complexity of slice functions ⋮ Lower bounds on monotone complexity of the logical permanent

Cites Work

• Unnamed Item
• 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
• Complexity of monotone networks for Boolean matrix product
• Monotone switching circuits and Boolean matrix product
• 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
• Complexity of Monotone Networks for Computing Conjunctions
• An Improved Lower Bound for Sorting Networks

This page was built for publication: Boolean functions whose monotone complexity is of size \(n^ 2\) / log n