Some remarks on Boolean sums

DOI10.1007/BF00268321MaRDI QIDQ1133518zbMATH OpenFDO

Authors K. Mehlhorn

Publication date 1979

Published in Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

Boolean functionslower boundmonotonous network complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Cites work

• scientific article; zbMATH DE number 3387244 (Why is no real title available?)
• Monotone switching circuits and Boolean matrix product
• On another Boolean matrix
• On Graphs that do not Contain a Thomsen Graph

Cited in

(11)

• An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
• A method for obtaining efficient lower bounds for monotone complexity
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
• Cancellation-free circuits in unbounded and bounded depth
• On algorithm complexity
• A very simple function that requires exponential size read-once branching programs.
• Separating OR, SUM, and XOR circuits
• On Negations in Boolean Networks
• Lower bounds for tropical circuits and dynamic programs
• On a small class of Boolean sums

This page was built for publication: Some remarks on Boolean sums

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