The Power of Negative Thinking in Multiplying Boolean Matrices
From MaRDI portal
Publication:4081156
DOI10.1137/0204027zbMath0318.94040OpenAlexW2020707942MaRDI QIDQ4081156
Publication date: 1975
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0204027
Related Items
On the optimality of Bellman-Ford-Moore shortest path algorithm, The monotone circuit complexity of Boolean functions, Switching functions whose monotone complexity is nearly quadratic, Negation can be exponentially powerful, A lower bound for the computational complexity of a set of disjunctives in a monotone basis, Lower bounds for monotone \(q\)-multilinear Boolean circuits, A fast output-sensitive algorithm for Boolean matrix multiplication, Unnamed Item, 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, Bounds for Semi-disjoint Bilinear Forms in a Unit-Cost Computational Model, Small normalized circuits for semi-disjoint bilinear forms require logarithmic and-depth, Unnamed Item, On Negations in Boolean Networks, Lower bounds on monotone complexity of the logical permanent
