TY - GEN

T1 - A lower bound for the size of syntactically multilinear arithmetic circuits

AU - Raz, Ran

AU - Shpilka, Amir

AU - Yehudayoff, Amir

PY - 2007/12/1

Y1 - 2007/12/1

N2 - We construct an explicit polynomial f(x1,..., xn), with coefficients in {0,1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Ω(n4/3/ log 2 n). The lower bound holds over any field.

AB - We construct an explicit polynomial f(x1,..., xn), with coefficients in {0,1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Ω(n4/3/ log 2 n). The lower bound holds over any field.

UR - http://www.scopus.com/inward/record.url?scp=46749150631&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=46749150631&partnerID=8YFLogxK

U2 - 10.1109/FOCS.2007.4389514

DO - 10.1109/FOCS.2007.4389514

M3 - Conference contribution

AN - SCOPUS:46749150631

SN - 0769530109

SN - 9780769530109

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 438

EP - 448

BT - Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007

T2 - 48th Annual Symposium on Foundations of Computer Science, FOCS 2007

Y2 - 20 October 2007 through 23 October 2007

ER -