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)

zbMATH Keywords

lower boundBoolean functionsmonotonous 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 Graphs that do not Contain a Thomsen Graph
• On another Boolean matrix

Cited in

(11)

• Lower bounds for tropical circuits and dynamic programs
• Separating OR, SUM, and XOR circuits
• On algorithm complexity
• A very simple function that requires exponential size read-once branching programs.
• \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
• On Negations in Boolean Networks
• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• 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
• A method for obtaining efficient lower bounds for monotone complexity
• 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)