Lower bound for monotone Boolean convolution

2017/08/11 by Mike Paterson, Paterson, Mike S.
Computer Science · #Complexity and Algorithms in Graphs #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #Quantum Computing Algorithms and Architecture

paper · pdf · doi:10.48550/arxiv.1708.03523

openalex publication_date 2017/08/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Any monotone Boolean circuit computing the n-dimensional Boolean convolution requires at least n² and-gates. This precisely matches the obvious upper bound.

Related

• Constant-depth circuits vs. monotone circuits
• Addition is exponentially harder than counting for shallow monotone\n circuits
• Negations are powerful even in small depth
• Topological aspects of Boolean functions
• Learning circuits with few negations