An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
From MaRDI portal
Publication:1066118
DOI10.1016/0304-3975(85)90030-1zbMath0577.94015WikidataQ67224712 ScholiaQ67224712MaRDI QIDQ1066118
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
68Q25: Analysis of algorithms and problem complexity
Related Items
Unnamed Item, Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth, Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution, 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