On the monotone complexity of the shift operator

Igor S. Sergeev

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 parti…