An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution

DOI10.1016/0304-3975(85)90030-1zbMath0577.94015OpenAlexW2089119058WikidataQ67224712 ScholiaQ67224712MaRDI QIDQ1066118

Norbert Blum

Publication date: 1985

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

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90030-1

zbMATH Keywords

normal formBoolean functionBoolean convolutionand-gateBoolean vector

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items

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 ⋮ On Negations in Boolean Networks

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• On another Boolean matrix
• 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
• Shifting Graphs and Their Applications
• Complexity of Monotone Networks for Computing Conjunctions