Weights at the Bottom Matter When the Top is Heavy

Proving super-polynomial lower bounds against depth-2 threshold circuits of the form THR o 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 o MAJ circuits were shown by Razborov and Sherstov (FOCS'08) even for computing functions in depth-3 AC0. Yet, no separation among the two depth-2 threshold circuit classes were known since the seminal work of Goldmann Hastad and Razborov from the early nineties.

In this work, we provide the first exponential separation between THR o MAJ and THR o THR answering an open problem explicitly posed by Hansen and Podolskii (Complexity'10). We achieve this by showing that a simple function f on n bits, which is a linear-size decision list of `Equalities', has exponentially large "sign rank". It follows, by a well-known result, that THR o MAJ circuits need exponential size to compute f which can easily be computed by THR o THR circuits of only linear size.

Additionally, our function f yields new communication complexity class separations. In particular, f lies in the class P^MA. As f has large sign-rank, it shows that P^MA is not contained in UPP, resolving a recent open problem of  Goos, Pitassi and Watson (ICALP'16).

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.

(Joint work with my Ph.D. student Nikhil Mande.)