ECCC-Report TR18-062https://eccc.weizmann.ac.il/report/2018/062Comments and Revisions published for TR18-062en-usSat, 07 Apr 2018 14:13:57 +0300
Paper TR18-062
| A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits |
Suryajith Chillara,
Christian Engels,
Nutan Limaye,
Srikanth Srinivasan
https://eccc.weizmann.ac.il/report/2018/062We study the size blow-up that is necessary to convert an algebraic circuit of product-depth $\Delta+1$ to one of product-depth $\Delta$ in the multilinear setting.
We show that for every positive $\Delta = \Delta(n) = o(\log n/\log \log n),$ there is an explicit multilinear polynomial $P^{(\Delta)}$ on $n$ variables that can be computed by a multilinear formula of product-depth $\Delta+1$ and size $O(n)$, but not by any multilinear circuit of product-depth $\Delta$ and size less than $\exp(n^{\Omega(1/\Delta)})$. This result is tight up to the constant implicit in the double exponent for all $\Delta = o(\log n/\log \log n).$
This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who prove a quasipolynomial separation for constant-depth multilinear circuits, and a result of Kayal, Nair and Saha (STACS 2016) who give an exponential separation in the case $\Delta = 1.$
Our separating examples may be viewed as algebraic analogues of variants of the Graph Reachability problem studied by Chen, Oliveira, Servedio and Tan (STOC 2016), who used them to prove lower bounds for constant-depth Boolean circuits.Sat, 07 Apr 2018 14:13:57 +0300https://eccc.weizmann.ac.il/report/2018/062