Title: A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
Abstract: We construct an explicit polynomial $f(x_1,\dots,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^2n)$. The lower bound holds over any field.
Publication Year: 2008
Publication Date: 2008-01-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 50
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot