On the complexity of slice functions

AbstractBy a result of Berkowitz (1982), the monotone circuit complexity of slice functions cannot be much larger than the circuit (combinational) complexity of these functions for arbitrary complete bases. This result strengthens the importance of the theory of monotone circuits. We show in this paper that monotone circuits for slice functions can be understood as special circuits called set circuits. Here, disjunction and conjunction are replaced by set union and set intersection. All the main methods known for proving lower bounds on the monotone complexity of Boolean functions fail to work in their present form for slice functions. Furthermore, we show that the canonical slice functions of the Boolean convolution, the Nechiporuk Boolean sums, and the clique function can be computed with a linear number of gates