Functions in arithmetic NC1 are known to have equivalent constant
width polynomial degree circuits, but the converse containment is
unknown. In a partial answer to this question, we show that syntactic
multilinear circuits of constant width and polynomial degree can be
depth-reduced, though the resulting circuits need not be ... more >>>

We prove a lower bound of $\Omega(n^2/\log^2 n)$ on the size of any syntactically multilinear arithmetic circuit computing some explicit multilinear polynomial $f(x_1, \ldots, x_n)$. Our approach expands and improves upon a result of Raz, Shpilka and Yehudayoff [RSY08], who proved a lower bound of $\Omega(n^{4/3}/\log^2 n)$ for the same ... more >>>