Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

Abstract

We show that any $n$-variate polynomial computable by a syntactically multilinear circuit of size $\mathrm{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~\cite{T15} 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~\cite{RY09}, 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 $\mathrm{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)$.