Addition is exponentially harder than counting for shallow monotone circuits.
X. Chen and I. Oliveira and R. Servedio.
In 49th Annual Symposium on Foundations of Computer Science (STOC), 2017, to appear.


Abstract: Let $\smash{\UU_{k,N}}$ denote the Boolean function which takes as input $k$ strings of $N$ bits each, representing $k$ numbers $a^{(1)},\dots,a^{(k)}$ in $\{0,1,\dots,2^{N}-1\}$, and outputs 1 if and only if $\smash{a^{(1)} + \cdots + a^{(k)} \geq 2^N.}$ Let $\THR_{t,n}$ denote a \emph{monotone unweighted threshold gate}, i.e., the Boolean function which takes as input a single string $x \in \{0,1\}^n$ and outputs $1$ if and only if $x_1 + \cdots + x_n \geq t$. The \mbox{function} $\UU_{k,N}$ may be viewed as a monotone function that performs addition, and $\THR_{t,n}$ may be viewed as a monotone gate that performs counting. We refer to circuits that are composed of $\THR$ gates as \emph{monotone majority circuits.}

The main result of this paper is an exponential lower bound on the size of bounded-depth monotone majority circuits that compute $\UU_{k,N}$. More precisely, we show that for any constant $d \geq 2$, any depth-$d$ monotone majority circuit that computes $\UU_{d,N}$ must have size $\smash{2^{\Omega(N^{1/d})}}$. As $\UU_{k,N}$ can be computed by a single monotone \emph{weighted} threshold gate (that uses exponentially large weights), our lower bound implies that constant-depth monotone majority circuits require exponential size to simulate monotone weighted~threshold gates. This answers a question posed by Goldmann and Karpinski (STOC'93) and recently restated by H\aa stad (2010, 2014). We also show that our lower bound is essentially best possible, by constructing a depth-$d$, size-$\smash{2^{O(N^{1/d})}}$ monotone majority circuit for $\UU_{d,N}$.

As a corollary of our lower bound, we significantly strengthen a classical theorem in circuit complexity due to Ajtai and Gurevich (JACM'87). They exhibited a monotone function that~is in $\mathsf{AC}^0$ but requires super-polynomial size for any constant-depth monotone circuit composed~of unbounded fan-in $\AND$ and $\OR$ gates. We describe a monotone function that is in depth-$3$ $\mathsf{AC}^0$ but requires \emph{exponential} size monotone circuits of any constant depth, even if the circuits are composed of $\THR$ gates.


pdf of conference version

Link to full version on ArXiV


Back to main papers page