TR06-060 Authors: Ran Raz, Amir Shpilka, Amir Yehudayoff

Publication: 4th May 2006 20:26

Downloads: 1867

Keywords:

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.