Switching functions whose monotone complexity is nearly quadratic

DOI10.1016/0304-3975(79)90008-2MaRDI QIDQ1133519zbMATH OpenOpenAlexFDO

Authors Ingo Wegener

Publication date 1979

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

Full work available at URL https://doi.org/10.1016/0304-3975(79)90008-2

zbMATH Keywords

complexity of Boolean functionsmonotonous switching circuitsproducts of Boolean matrices

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• Complexity of monotone networks for Boolean matrix product
• Gaussian elimination is not optimal
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)
• Monotone switching circuits and Boolean matrix product
• The Power of Negative Thinking in Multiplying Boolean Matrices

Cited in

(8)

• 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
• A method for obtaining efficient lower bounds for monotone complexity
• On another Boolean matrix
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• A counterexample to a conjecture of Schnorr referring to monotone networks
• On algorithm complexity
• On Negations in Boolean Networks

This page was built for publication: Switching functions whose monotone complexity is nearly quadratic

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1133519)