Addition is exponentially harder than counting for shallow monotone circuits.
X. Chen and I. Oliveira and R. Servedio.
In 49th Annual Symposium on Theory of Computing (STOC), 2017, pp. 1232--1245.

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