Switching functions whose monotone complexity is nearly quadratic

DOI10.1016/0304-3975(79)90008-2zbMath0421.94023OpenAlexW2041228989MaRDI QIDQ1133519

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)

Related Items (8)

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 ⋮ On algorithm complexity ⋮ A counterexample to a conjecture of Schnorr referring to monotone networks ⋮ On Negations in Boolean Networks ⋮ 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

Cites Work

• Unnamed Item
• Complexity of monotone networks for Boolean matrix product
• Monotone switching circuits and Boolean matrix product
• Gaussian elimination is not optimal
• The Power of Negative Thinking in Multiplying Boolean Matrices

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