Proving super-polynomial lower bounds against depth-2 threshold circuits of the form \mathsf TH R \mathsf TH R 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 TH R \mathsf MA J circuits were shown by Razborov and Sherstov (SIAM J. Comput., 2010) even for computing functions in depth-3 \mathsf A C 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 TH R \mathsf MA J and \mathsf TH R \mathsf TH R , 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 ( n 1 4 ) . It follows, by a well-known result that \mathsf TH R \mathsf MA J circuits need size 2 ( n 1 4 ) to compute f , while it is not difficult to observe that f can be computed by \mathsf TH R \mathsf TH R circuits of only linear size. Our result, thus, suggest that the sign rank method alone is unlikely to prove strong lower bounds against \mathsf TH R \mathsf TH R 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 UP P , 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 XO R function. This requires novel use of approximation theoretic tools.