Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-083 | 5th May 2017 23:57

Weights at the Bottom Matter When the Top is Heavy


Authors: Arkadev Chattopadhyay, Nikhil Mande
Publication: 6th May 2017 00:47
Downloads: 130


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.

ISSN 1433-8092 | Imprint