Amplification of Bounded Depth Monotone Read-Once Boolean Formulae

DOI10.1137/0220003MaRDI QIDQ3204041zbMATHOpenAlexFDO

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

zbMATH Keywords

Boolean functionamplification functionmonotone read-once formulae

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

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

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)