On another Boolean matrix

DOI10.1016/0304-3975(80)90034-1MaRDI QIDQ1137982zbMATH OpenOpenAlexFDO

Authors Nicholas 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

homogeneous monotone Boolean functionsmonotone Boolean networktwo-input gates

Mathematics Subject Classification ID

Cites work

• scientific article; zbMATH DE number 3387244 (Why is no real title available?)
• On a problem of K. Zarankiewicz
• On Graphs that do not Contain a Thomsen Graph
• On the difference between consecutive primes
• Switching functions whose monotone complexity is nearly quadratic
• The minimum number of edges in graphs with prescribed paths

Cited in

(12)

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

This page was built for publication: On another Boolean matrix

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1137982)