X. Chen and I. Oliveira and R. Servedio.

In

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