No label defined (Q3335688)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 3867233
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3867233 |
Statements
1984
0 references
combinational complexity
0 references
Monotone Boolean functions
0 references
Boolean networks
0 references
nonlinear lower bounds
0 references
monotone network complexity
0 references
Boolean convolution
0 references
generalized Boolean matrix product
0 references
0.93236387
0 references
0.92584383
0 references
0.9190672
0 references
[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.
0 references