Abstract
We show that any n-variate polynomial computable by a syntactically multilinear circuit of size poly(n) can be computed by a syntactically multilinear depth-4 circuit of size at most exp({O(\sqrt{nlog n}). For degree d = omega(n/log n), this improves upon the upper bound of exp({O(\sqrt{d}\log n)} obtained by Tavenas for general (non-multilinear) 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({Omega(\sqrt{nlog n})} proved by Raz and Yehudayoff, and thus cannot be improved further in the exponent.
Based on joint work with Rafael Oliveira and Ramprasad Saptharishi.