On Computing Multilinear Polynomials Using Multir ic Depth Four Circuits In this paper, we are interested in understanding the complexity of computing multilinear polynomials using depth four circuits in which polynomial computed at every node has a bound on the individual degree of r (referred to as multiric circuits). The goal of this study is to make progress towards proving superpolynomial lower bounds for general depth four circuits computing multilinear polynomials, by proving better and better bounds as the value of r increases. Recently, Kayal, Saha and Tavenas (Theory of Computing, 2018) showed that any depth four arithmetic circuit of bounded individual degree r computing a multilinear polynomial on nO(1) variables and degree d  o(n), must have size at least (nr1.1)sqrtdr when r is o(d) and is strictly less than n11.1. This bound however deteriorates with increasing r. It is a natural question to ask if we can prove a bound that does not deteriorate with increasing r or a bound that holds for a larger regime of r. We here prove a lower bound which does not deteriorate with r , however for a specific instance of d  d (n) but for a wider range of r. Formally, we show that there exists an explicit polynomial on nO(1) variables and degree xcex98(log2(n)) such that any depth four circuit of bounded individual degree r u003c n0.2 must have size at least exp(xcexa9 (log2 n)). This improvement is obtained by suitably adapting the complexity measure of Kayal et al. (Theory of Computing, 2018). This adaptation of the measure is inspired by the complexity measure used by Kayal et al. (SIAM J. Computing, 2017).

Towards Optimal Depth Reductions for Syntactically Multilinear Circuits We show that any nvariate polynomial computable by a syntactically multilinear circuit of size operatornamepoly(n) can be computed by a depth4 syntactically multilinear (SigmaPiSigmaPi) circuit of size at most expleft(Oleft(sqrtnlog nright)right). For degree d  omega(nlog n), this improves upon the upper bound of expleft(O(sqrtdlog n)right) obtained by TavenasciteT15 for general circuits, and is known to be asymptotically optimal in the exponent when d u003c nepsilon for a small enough constant epsilon. Our upper bound matches the lower bound of expleft(Omegaleft(sqrtnlog nright)right) proved by Raz and YehudayoffciteRY09, and thus cannot be improved further in the exponent. Our results hold over all fields and also generalize to circuits of small individual degree.  :111,generally, we show that an nvariate polynomial computable by a syntactically multilinear circuit of size operatornamepoly(n) can be computed by a syntactically multilinear circuit of productdepth Delta of size at most expleft(Oleft(Delta cdot (nlog n)1Delta cdot log nright)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 oleft(left(nlog nright)1Deltacdot log nright).