A 2.5 n lower bound on the monotone network complexity of T^ n_ 3

DOI10.1007/BF00264232zbMATH Open0545.94021OpenAlexW2320924696MaRDI QIDQ798294FDOQ798294

Authors: Paul E. Dunne 

Publication date: 1985

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00264232

Recommendations

• A Lower Bound of the Number of Threshold Functions
• scientific article; zbMATH DE number 3867233
• scientific article
• scientific article; zbMATH DE number 3906395
• On the complexity of monotone circuits for threshold symmetric Boolean functions

zbMATH Keywords

threshold functionmonotone Boolean functionmonotone Boolean networkmonotone network complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (7)

• On the complexity of monotone circuits for threshold symmetric Boolean functions
• An n3/2 lower bound on the monotone network complexity of the Boolean convolution
• Directed monotone contact networks for threshold functions
• A Lower Bound of the Number of Threshold Functions
• Comment on Kochol's paper ``Efficient monotone circuits for threshold functions
• A Boolean function requiring 3n network size
• An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution

This page was built for publication: A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\)

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