A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
Ran Raz, Amir Shpilka, Amir Yehudayoff · 2007
We construct an explicit polynomial f(x1,..., xn), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Omega{n4/3log2n} The lower bound holds over any field.