Amplification of Bounded Depth Monotone Read-Once Boolean Formulae

DOI10.1137/0220003zbMATH Open0716.68043OpenAlexW2082003776MaRDI QIDQ3204041FDOQ3204041

Authors: Qian-Ping Gu, A. Maruoka 

Publication date: 1991

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0220003

Recommendations

• On a relation between the depth and complexity of monotone Boolean formulas
• On the readability of monotone Boolean formulae
• On the Readability of Monotone Boolean Formulae
• Depth-independent lower bounds on the communication complexity of read-once Boolean formulas
• The monotone circuit complexity of Boolean functions
• Size-depth tradeoffs for Boolean formulae
• scientific article; zbMATH DE number 4193610
• scientific article; zbMATH DE number 4095386
• An improved complexity hierarchy on the depth of Boolean functions

zbMATH Keywords

Boolean functionamplification functionmonotone read-once formulae

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (1)

• The Boolean functions computed by random Boolean formulas or how to grow the right function

This page was built for publication: Amplification of Bounded Depth Monotone Read-Once Boolean Formulae

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