ECCC-Report TR17-083https://eccc.weizmann.ac.il/report/2017/083Comments and Revisions published for TR17-083en-usMon, 18 Sep 2017 23:28:30 +0300
Revision 1
| Weights at the Bottom Matter When the Top is Heavy |
Arkadev Chattopadhyay,
Nikhil Mande
https://eccc.weizmann.ac.il/report/2017/083#revision1Proving 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.Mon, 18 Sep 2017 23:28:30 +0300https://eccc.weizmann.ac.il/report/2017/083#revision1
Paper TR17-083
| Weights at the Bottom Matter When the Top is Heavy |
Arkadev Chattopadhyay,
Nikhil Mande
https://eccc.weizmann.ac.il/report/2017/083Proving 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.Sat, 06 May 2017 00:47:33 +0300https://eccc.weizmann.ac.il/report/2017/083