ECCC-Report TR06-060https://eccc.weizmann.ac.il/report/2006/060Comments and Revisions published for TR06-060en-usThu, 04 May 2006 20:26:32 +0300
Paper TR06-060
| A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits |
Ran Raz,
Amir Shpilka,
Amir Yehudayoff
https://eccc.weizmann.ac.il/report/2006/060We 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.
Thu, 04 May 2006 20:26:32 +0300https://eccc.weizmann.ac.il/report/2006/060