Negation is Powerless for Boolean Slice Functions
This paper deals with upper bounds for the complexity of minimal size Boolean circuits. The question is, how much the complexity of a monotone circuit exceeds the complexity of the circuit over the universal basis \(\{\wedge,\vee,\neg \}\). If the kth slice function of a Boolean function \(f(x_ 1,...,x_ n)\) is defined to be equal to (i) \(f(x_ 1,...,x_ n)\) if exactly k inputs are 1, (ii) 0 if fewer than k inputs are one, and (iii) 1 if more than k inputs are one, then the function f is well represented by its \(n+1\) slices (they are of course monotone functions). The author shows that \[ C_{\wedge,\vee}(F)\leq 2C_{\wedge,\vee,\neg}(F)+O(n(\log n)^ 2), \] for all slice function sets F. This result differs in the additive term from the previously known \(O(n^ 2 \log n)\). The proof is based on the construction of monotone subcircuits that can merge two sorted lists of length m in O(m log m) gates.
- On the minimum number of negations leading to super-polynomial savings
- On the complexity of slice functions
- More on the complexity of slice functions
- The complexity of central slice functions
- On monotone simulations on nonmonotone networks
- \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
- On \(\epsilon\)-sensitive monotone computations
- Fast monotone summation over disjoint sets
- Fast Möbius inversion in semimodular lattices and ER-labelable posets
- scientific article; zbMATH DE number 3889430 (Why is no real title available?)
- On Negations in Boolean Networks
- On derandomization and average-case complexity of monotone functions
- Reductions for Monotone Boolean Circuits
This page was built for publication: Negation is Powerless for Boolean Slice Functions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4726175)