A new lower bound on the monotone network complexity of Boolean sums

DOI10.1007/BF00263988MaRDI QIDQ1137007zbMATH OpenFDO

Authors Ingo Wegener

Publication date 1980

Published in Acta Informatica (Search for Journal in Brave)

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

zbMATH Keywords

Boolean sumslower boundmonotone network complexity of Boolean functions

Mathematics Subject Classification ID

Cited in

(7)

• An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
• Lower bounds on monotone complexity of the logical permanent
• 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
• A very simple function that requires exponential size read-once branching programs.
• On Negations in Boolean Networks

This page was built for publication: A new lower bound on the monotone network complexity of Boolean sums

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