On the complexity of slice functions (Q1066866)

By results of Razborov negations can be very powerful for Boolean circuits. But for the class of slice functions negations are almost powerless. Hence each hard function has a hard slice. Lower bounds on the monotone circuit complexity of slice functions imply lower bounds on the circuit complexity of these functions. The structure of slice functions is investigated and efficient algorithms for some slice functions are presented.