Complexity of monotone networks for Boolean matrix product
From MaRDI portal
Publication:1218267
DOI10.1016/0304-3975(75)90009-2zbMath0307.68031MaRDI 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
68Q25: Analysis of algorithms and problem complexity
Related Items
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, 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, On the complexity of 2-output Boolean networks, Boolean functions whose monotone complexity is of size \(n^ 2\) / log n, A lower bound on the number of additions in monotone computations, Realizing Boolean functions on disjoint sets of variables, On Negations in Boolean Networks
Cites Work