A lower bound for the size of syntactically multilinear arithmetic circuits

Ran Raz, Amir Shpilka, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Pages438-448
Number of pages11
DOIs
StatePublished - Dec 1 2007
Externally publishedYes
Event48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States
Duration: Oct 20 2007Oct 23 2007

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (Print)0272-5428

Other

Other48th Annual Symposium on Foundations of Computer Science, FOCS 2007
CountryUnited States
CityProvidence, RI
Period10/20/0710/23/07

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'A lower bound for the size of syntactically multilinear arithmetic circuits'. Together they form a unique fingerprint.

  • Cite this

    Raz, R., Shpilka, A., & Yehudayoff, A. (2007). A lower bound for the size of syntactically multilinear arithmetic circuits. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007 (pp. 438-448). [4389514] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2007.4389514