Relating monotone formula size and monotone depth of Boolean functions

DOI10.1016/0020-0190(83)90011-XMaRDI QIDQ1835900zbMATH OpenFDO

Authors Ingo Wegener

Publication date 1983

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(83)90011-X

zbMATH Keywords

computational complexitydepthformula sizemonotone basistrade-off- results

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cites work

• Boolean functions whose monotone complexity is of size \(n^ 2\) / log n
• scientific article; zbMATH DE number 3566175 (Why is no real title available?)

Cited in

(15)

• Monotone circuits for monotone weighted threshold functions
• Strengthening convex relaxations of 0/1-sets using Boolean formulas
• Certain sufficient conditions of uniformity for systems of functions of many-valued logic
• Applications of matrix methods to the theory of lower bounds in computational complexity
• Lower bounds for Boolean circuits of bounded negation width
• A generalization of Spira's theorem and circuits with small segregators or separators
• A generalization of Spira's theorem and circuits with small segregators or separators
• Uniformity of a certain systems of functions of many-valued logic
• Lower Bounds for DeMorgan Circuits of Bounded Negation Width
• How to share an NP statement or combiners for zero-knowledge proofs
• NIZK amplification via leakage-resilient secure computation
• Secret sharing, slice formulas, and monotone real circuits
• Replaceability and computational equivalence for monotone boolean functions
• Translating propositional extended conjunctions of Horn clauses into Boolean circuits
• W-hierarchies defined by symmetric gates

This page was built for publication: Relating monotone formula size and monotone depth of Boolean functions

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