ECCC-Report TR19-019https://eccc.weizmann.ac.il/report/2019/019Comments and Revisions published for TR19-019en-usTue, 19 Feb 2019 16:27:13 +0200
Paper TR19-019
| Towards Optimal Depth Reductions for Syntactically Multilinear Circuits |
Mrinal Kumar,
Rafael Mendes de Oliveira,
Ramprasad Saptharishi
https://eccc.weizmann.ac.il/report/2019/019We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a depth-$4$ syntactically multilinear ($\Sigma\Pi\Sigma\Pi$) circuit of size at most $\exp\left({O\left(\sqrt{n\log n}\right)}\right)$. For degree $d = \omega(n/\log n)$, this improves upon the upper bound of $\exp\left({O(\sqrt{d}\log n)}\right)$ obtained by Tavenas (MFCS 2015) for general circuits, and is known to be asymptotically optimal in the exponent when $d < n^{\epsilon}$ for a small enough constant $\epsilon$. Our upper bound matches the lower bound of $\exp\left({\Omega\left(\sqrt{n\log n}\right)}\right)$ proved by Raz and Yehudayoff (CC 2009), and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree.
More generally, we show that an $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathop{poly}(n)$ can be computed by a syntactically multilinear circuit of product-depth $\Delta$ of size at most $\exp\left(O\left(\Delta \cdot (n/\log n)^{1/\Delta} \cdot \log n\right)\right)$. It follows from the lower bounds of Raz and Yehudayoff (CC 2009) that in general, for constant $\Delta$, the exponent in this upper bound is tight and cannot be improved to $o\left(\left(n/\log n\right)^{1/\Delta}\cdot \log n\right)$.
Tue, 19 Feb 2019 16:27:13 +0200https://eccc.weizmann.ac.il/report/2019/019