On the monotone complexity of the shift operator

2019/05/26 by Igor S. Sergeev, I. S. Sergeev, Sergeev, Igor S.
Computer Science · Mathematics · #Coding theory and cryptography #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Mathematical Analysis and Transform Methods #Matrix Theory and Algorithms #cs.CC

paper · pdf · doi:10.48550/arxiv.1905.10747

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

openalex publication_date 2019/05/26 · arxiv created 2020/06/30 · arxiv updated 2020/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 Θ(qnlog n). In particular, we obtain an alternative way to prove the known complexity bound Θ(nlog n) for the monotone shift operator on n boolean inputs.

Related

• Lower bound for monotone Boolean convolution
• Computing the Best Case Energy Complexity of Satisfying Assignments in Monotone Circuits
• On Lower Bounds for Constant Width Arithmetic Circuits
• Some Extensions of the Inversion Complexity of Boolean Functions
• Learning circuits with few negations