A LOWER BOUND FOR THE SIZE OF SYNTACTICALLY MULTILINEAR ARITHMETIC CIRCUITS
We construct an explicit polynomial f(x(1),..., x(n)), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Omega(n(4/3)/log(2)n). The lower bound holds over any field.
lower bounds arithmetic circuits explicit constructions