scientific article; zbMATH DE number 3867233

From MaRDI portal
Publication:3335688





[For the entire collection see Zbl 0538.00005.] Monotone Boolean functions may be computed in Boolean networks over the monotone basis \(\Omega_ m=\{\wedge,\vee \}\). For many explicitly defined functions \(f:\{0,1\}^ n\to \{0,1\}^ n\) one is able to prove nonlinear lower bounds on their monotone network complexity. Here the methods used for these bounds are discussed. An \(\Omega(n^{3/2})\)-bound for the Boolean convolution [J. Weiß: Eine \(n^{3/2}\)-untere Schranke für die Boolesche Konvolution. Diplomarbeit, Univ. Bielefeld (1982)] and the largest known bound, an \(\Omega(n^ 2\log^{-1}n)\)- bound for a generalized Boolean matrix product, are described in more detail.




Cited in
(35)








This page was built for publication:

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