scientific article; zbMATH DE number 3867233
[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.
- scientific article; zbMATH DE number 4193610
- scientific article; zbMATH DE number 4095386
- scientific article; zbMATH DE number 4008289
- The monotone circuit complexity of Boolean functions
- Bounds for the average-case complexity of monotone Boolean functions
- Lower bounds for the complexity of restrictions of Boolean functions
- scientific article; zbMATH DE number 3900678
- scientific article; zbMATH DE number 3999837
- scientific article; zbMATH DE number 4208009
- Lower bounds on the formula complexity of a linear Boolean function
- An \(\Omega (n^{4/3})\) lower bound on the monotone network complexity of the \(n\)-th degree convolution
- The monotone circuit complexity of Boolean functions
- Through the mincing machine with a Boolean layer cake: nonstandard computations over Boolean circuits in the lower-bounds-to-circuit-size complexity proving
- On monotone simulations on nonmonotone networks
- Bounds for the average-case complexity of monotone Boolean functions
- Monotone Boolean dualization is in co-NP\([\log^{2}n]\).
- Proof complexity of monotone branching programs
- The monotone circuit complexity of quadratic Boolean functions
- Applications of matrix methods to the theory of lower bounds in computational complexity
- Towards an almost quadratic lower bound on the monotone circuit complexity of the Boolean convolution
- scientific article; zbMATH DE number 4172377 (Why is no real title available?)
- scientific article; zbMATH DE number 3867232 (Why is no real title available?)
- scientific article; zbMATH DE number 4204284 (Why is no real title available?)
- scientific article; zbMATH DE number 4208009 (Why is no real title available?)
- On Negations in Boolean Networks
- An n3/2 lower bound on the monotone network complexity of the Boolean convolution
- A Gödel Theorem on Network Complexity Lower Bounds
- scientific article; zbMATH DE number 3943711 (Why is no real title available?)
- scientific article; zbMATH DE number 4002123 (Why is no real title available?)
- scientific article; zbMATH DE number 4008289 (Why is no real title available?)
- scientific article; zbMATH DE number 4008290 (Why is no real title available?)
- scientific article; zbMATH DE number 4049557 (Why is no real title available?)
- scientific article; zbMATH DE number 4095386 (Why is no real title available?)
- scientific article; zbMATH DE number 4102490 (Why is no real title available?)
- scientific article; zbMATH DE number 42045 (Why is no real title available?)
- scientific article; zbMATH DE number 176866 (Why is no real title available?)
- scientific article; zbMATH DE number 176870 (Why is no real title available?)
- scientific article; zbMATH DE number 1498465 (Why is no real title available?)
- Ceilings of monotone Boolean functions
- Switching functions whose monotone complexity
- Linear Transformations in Boolean Complexity Theory
- On the monotone circuit complexity of quadratic Boolean functions
- Reductions for Monotone Boolean Circuits
- A Boolean function requiring 3n network size
- A 2.5 n lower bound on the monotone network complexity of \(T^ n_ 3\)
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)