Addition is exponentially harder than counting for shallow monotone circuits
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio · 2017
Let Addk,N denote the Boolean function which takes as input k strings of N bits each, representing k numbers a(1),…,a(k) in {0,1,…,2N-1}, and outputs 1 if and only if a(1) + … + a(k) ≥ 2N. Let MAJt,n denote a monotone unweighted threshold gate, i.e., the Boolean function which takes as input a single string x Ε {0,1}n and outputs 1 if and only if x1 + … + xn ≥ t. The function Addk,N may be viewed as a monotone function that performs addition, and MAJt,n may be viewed as a monotone gate that performs counting. We refer to circuits that are composed of MAJ gates as monotone majority circuits.