Proving super-polynomial lower bounds against depth-2 threshold circuits of the form $\mathsf{THR} \circ \mathsf{THR}$ is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of $\mathsf{THR} \circ \mathsf{MAJ}$ circuits were shown by Razborov and Sherstov (SIAM J. Comput., 2010) even for computing functions in depth-3 $\mathsf{AC}^0$. Yet, no separation among the two depth-2 threshold circuit classes was known.
In this work, we provide the first exponential separation between $\mathsf{THR} \circ \mathsf{MAJ}$ and $\mathsf{THR} \circ \mathsf{THR}$, answering an open problem explicitly posed by Hansen and Podolskii (CCC, 2010). We achieve this by showing a simple function $f$ on $n$ bits, which is a linear-sized decision list of "Equalities", has sign rank $2^{\Omega(n^{1/4})}$. It follows, by a well-known result that $\mathsf{THR} \circ \mathsf{MAJ}$ circuits need size $2^{\Omega(n^{1/4})}$ to compute $f$, while it is not difficult to observe that $f$ can be computed by $\mathsf{THR} \circ \mathsf{THR}$ circuits of only linear size. Our result, thus, suggest that the sign rank method alone is unlikely to prove strong lower bounds against $\mathsf{THR} \circ \mathsf{THR}$ circuits.
Additionally, our function $f$ yields new communication complexity class separations. In particular, $f$ lies in the class $\mathsf{P}^{\mathsf{MA}}$. As $f$ has large sign rank, this shows that $\mathsf{P}^{\mathsf{MA}} \nsubseteq \mathsf{UPP}$, resolving a recent open problem of Goos, Pitassi and Watson (ICALP, 2016).
The main technical ingredient of our work is to prove a strong sign rank lower bound for an $\mathsf{XOR}$ function. This requires novel use of approximation theoretic tools.
Polished previous version.
Added new section about implications on communication complexity class separations, resolving an open question of Goos, Pitassi and Watson (ICALP, 2016).
Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR of THR is a well-known open problem that represents a frontier of our understanding in boolean circuit complexity. By contrast, exponential lower bounds on the size of THR of MAJ circuits were shown by Razborov and Sherstov (SIAM J. Comput., 2010) even for computing functions in depth-3 AC^0. Yet, no separation among the two depth-2 threshold circuit classes were known. In fact, it is not clear a priori that they ought to be different. In particular, Goldmann, Hastad and Razborov (Computational Complexity, 1992) showed that MAJ of MAJ is identical to the class MAJ of THR.
In this work, we provide an exponential separation between THR of MAJ and THR of THR. We achieve this by showing a function f that is computed by linear size THR of THR circuits and yet has exponentially large sign rank. This, by a well-known result, implies that f requires exponentially large THR of MAJ circuits to be computed. Our result suggests that the sign rank method alone is unlikely to prove strong lower bounds against THR of THR circuits.
The main technical ingredient of our work is to prove a strong sign rank lower bound for an XOR function. This requires novel use of approximation theoretic tools.
