On another Boolean matrix

DOI10.1016/0304-3975(80)90034-1zbMath0429.94038OpenAlexW2056094722MaRDI QIDQ1137982

Nicholas J. Pippenger

Publication date: 1980

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(80)90034-1

zbMATH Keywords

monotone Boolean networkhomogeneous monotone Boolean functionstwo-input gates

Mathematics Subject Classification ID

Related Items

Separating OR, SUM, and XOR circuits, \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice, Some remarks on Boolean sums, Lower bounds for tropical circuits and dynamic programs, On a small class of Boolean sums, Lower bounds for monotone span programs, The minimum number of edges in graphs with prescribed paths, On Negations in Boolean Networks, Tropical Complexity, Sidon Sets, and Dynamic Programming, Cancellation-free circuits in unbounded and bounded depth, An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution

Cites Work

• Unnamed Item
• Switching functions whose monotone complexity is nearly quadratic
• The minimum number of edges in graphs with prescribed paths
• On Graphs that do not Contain a Thomsen Graph
• On a problem of K. Zarankiewicz
• On the difference between consecutive primes