scientific article; zbMATH DE number 3889430
From MaRDI portal
Publication:3221885
[For the entire collection see Zbl 0544.00022.] For an important subclass of all Boolean functions - the so called slice functions - the circuit complexity over complete bases or the monotone basis are nearly of the same size since pseudo complements can be computed efficiently. Here the complexity of pseudo complements and the complexity of some slices of important functions like Boolean convolution and clique functions are investigated. Furthermore some new models are introduced which lead to new possibilities of proving lower bounds on the circuit complexity of Boolean functions.
Recommendations
Cited in
(23)- 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
- A hierarchy of propositional Horn formuls
- The slice map problem and approximation properties
- Lower bounds on the area complexity of Boolean circuits
- The multiplicative complexity of quadratic boolean forms
- Functions with bounded symmetric communication complexity, programs over commutative monoids, and ACC
- Optimal bounds for the approximation of Boolean functions and some applications
- Graph complexity and slice functions
- \(\text{PI}_ k\) mass production and an optimal circuit for the Nečiporuk slice
- Bent functions and random Boolean formulas
- Interior and exterior functions of Boolean functions
- The powerset operator on abstract interpretations
- Negation is Powerless for Boolean Slice Functions
- Query complexity of Boolean functions on slices
- Query complexity of Boolean functions on the middle slice of the cube
- Sensitivity vs. block sensitivity (an average-case study)
- Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates
- A nonlinear lower bound on the practical combinational complexity
- An extension of Khrapchenko's theorem
- Prediction-preserving reducibility
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 Q3221885)