cs.CC
On the monotone complexity of the shift operator. We show that the complexity of minimal monotone circuits implementing a monotone version of the permutation operator on n boolean vectors of length q is Theta(qn log n) . In particular, we obtain an alternative way to prove the known complexity bound Theta(n log n) for the monotone shift operator on n boolean inputs.