An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
type: Item
instance of: scholarly article
title: An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
zbMATH Open document ID: 0577.94015
DOI: 10.1016/0304-3975(85)90030-1
author: Norbert Blum
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: The main result establishes an \(\Omega (n^{4/3})\) lower bound on the number of \(\wedge\)-gates in any monotone network computing Boolean convolution of two Boolean n-vectors. The proof is based on a normal form of monotone networks introduced by the author.
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3924678
zbMATH Keywords: Boolean function
zbMATH Keywords: and-gate
zbMATH Keywords: Boolean vector
zbMATH Keywords: Boolean convolution
zbMATH Keywords: normal form
Wikidata QID: Q67224712
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90030-1
OpenAlex ID: W2089119058
cites work: Q4190138
cites work: Q4133122
cites work: Some remarks on Boolean sums
cites work: Monotone switching circuits and Boolean matrix product
cites work: Q5656695
cites work: Complexity of monotone networks for Boolean matrix product
cites work: On another Boolean matrix
cites work: Shifting Graphs and Their Applications
cites work: Q4138141
cites work: Zwei lineare untere Schranken für die Komplexität Boolescher Funktionen
cites work: Complexity of Monotone Networks for Computing Conjunctions
cites work: A new lower bound on the monotone network complexity of Boolean sums
cites work: Switching functions whose monotone complexity is nearly quadratic
description: scientific article; zbMATH DE number 3924678