Complexity of monotone networks for Boolean matrix product
From MaRDI portal
Publication:1218267
DOI10.1016/0304-3975(75)90009-2zbMath0307.68031OpenAlexW2569195351MaRDI QIDQ1218267
Publication date: 1975
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: http://wrap.warwick.ac.uk/46302/7/WRAP_Paterson_cs-rr-002.pdf
Lua error in Module:PublicationMSCList at line 37: attempt to index local 'msc_result' (a nil value).
Related Items (19)
On the optimality of Bellman-Ford-Moore shortest path algorithm ⋮ The monotone circuit complexity of Boolean functions ⋮ A method for obtaining efficient lower bounds for monotone complexity ⋮ Switching functions whose monotone complexity is nearly quadratic ⋮ Negation can be exponentially powerful ⋮ Lower bounds for monotone \(q\)-multilinear Boolean circuits ⋮ A fast output-sensitive algorithm for Boolean matrix multiplication ⋮ On the complexity of 2-output Boolean networks ⋮ Boolean functions whose monotone complexity is of size \(n^ 2\) / log n ⋮ Towards an Almost Quadratic Lower Bound on the Monotone Circuit Complexity of the Boolean Convolution ⋮ On algorithm complexity ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ A lower bound on the number of additions in monotone computations ⋮ Realizing Boolean functions on disjoint sets of variables ⋮ Unnamed Item ⋮ On Negations in Boolean Networks ⋮ Replaceability and computational equivalence for monotone boolean functions ⋮ An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
Cites Work
This page was built for publication: Complexity of monotone networks for Boolean matrix product
