Monotone switching circuits and Boolean matrix product

DOI10.1007/BF02241983zbMath0323.94019OpenAlexW2330503368MaRDI QIDQ1224550

Zvi Galil, Kurt Mehlhorn

Publication date: 1976

Published in: Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02241983

Mathematics Subject Classification ID

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

• Unnamed Item

This page was built for publication: Monotone switching circuits and Boolean matrix product