  Let $U_{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 $a^{(1)} + \cdots +
a^{(k)} \geq 2^N.$ Let THR$_{t,n}$ denote a 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$. We refer
to circuits that are composed of THR gates as 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 $U_{k,N}$. More
precisely, we show that for any constant $d \geq 2$, any depth-$d$ monotone
majority circuit computing $U_{d,N}$ must have size
$\smash{2^{\Omega(N^{1/d})}}$. Since $U_{k,N}$ can be computed by a single
monotone 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
Hastad (2010, 2014). We also show that our lower bound is essentially best
possible, by constructing a depth-$d$, size-$2^{O(N^{1/d})}$ monotone majority
circuit for $U_{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 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$ AC$^0$ but
requires exponential size monotone circuits of any constant depth, even if the
circuits are composed of THR gates.
