Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-060 | 4th May 2006 00:00

A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

RSS-Feed




TR06-060
Authors: Ran Raz, Amir Shpilka, Amir Yehudayoff
Publication: 4th May 2006 20:26
Downloads: 3804
Keywords: 


Abstract:

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.



ISSN 1433-8092 | Imprint