On the monotone complexity of the shift operator

Abstract

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.

7 pages (in English); 7 pages (in Russian); ver. 2: abstract extended, and bibliography updated

References in corpus (2)

• Thin circulant matrices and lower bounds on the complexity of some Boolean operators
• Lower Bounds for Multiplication via Network Coding