Monotone switching circuits and Boolean matrix product
From MaRDI portal
Publication:1224550
DOI10.1007/BF02241983zbMath0323.94019OpenAlexW2330503368MaRDI QIDQ1224550
Publication date: 1976
Published in: Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02241983
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 ⋮ Some remarks on Boolean sums ⋮ Switching functions whose monotone complexity is nearly quadratic ⋮ Negation can be exponentially powerful ⋮ Lower bounds for monotone \(q\)-multilinear Boolean circuits ⋮ 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 ⋮ Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model ⋮ On algorithm complexity ⋮ Lower bounds for tropical circuits and dynamic programs ⋮ Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth ⋮ 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 ⋮ On the complexity of slice functions
Cites Work
This page was built for publication: Monotone switching circuits and Boolean matrix product