A lower bound for the size of syntactically multilinear arithmetic circuits

Ran Raz; Amir Shpilka; Amir Yehudayoff

doi:10.1109/FOCS.2007.4389514

A lower bound for the size of syntactically multilinear arithmetic circuits

Ran Raz, Amir Shpilka, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 Scopus citations

Abstract

We construct an explicit polynomial f(x₁,..., x_n), with coefficients in {0,1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Ω(n^4/3/ log ² n). The lower bound holds over any field.

Original language	English (US)
Title of host publication	Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007
Pages	438-448
Number of pages	11
DOIs	https://doi.org/10.1109/FOCS.2007.4389514
State	Published - 2007
Externally published	Yes
Event	48th Annual Symposium on Foundations of Computer Science, FOCS 2007 - Providence, RI, United States Duration: Oct 20 2007 → Oct 23 2007

Publication series

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

Other

Other	48th Annual Symposium on Foundations of Computer Science, FOCS 2007
Country/Territory	United States
City	Providence, RI
Period	10/20/07 → 10/23/07

All Science Journal Classification (ASJC) codes

General Engineering

Access to Document

10.1109/FOCS.2007.4389514

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). Article 4389514 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/FOCS.2007.4389514

@inproceedings{495e4d4d2a0e4f4097421427289c598a,

title = "A lower bound for the size of syntactically multilinear arithmetic circuits",

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.",

author = "Ran Raz and Amir Shpilka and Amir Yehudayoff",

year = "2007",

doi = "10.1109/FOCS.2007.4389514",

language = "English (US)",

isbn = "0769530109",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

pages = "438--448",

booktitle = "Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007",

note = "48th Annual Symposium on Foundations of Computer Science, FOCS 2007 ; Conference date: 20-10-2007 Through 23-10-2007",

}

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., 4389514, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 438-448, 48th Annual Symposium on Foundations of Computer Science, FOCS 2007, Providence, RI, United States, 10/20/07. https://doi.org/10.1109/FOCS.2007.4389514

A lower bound for the size of syntactically multilinear arithmetic circuits. / Raz, Ran; Shpilka, Amir; Yehudayoff, Amir.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2007. 2007. p. 438-448 4389514 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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

Y1 - 2007

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 -

A lower bound for the size of syntactically multilinear arithmetic circuits

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this