A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits

Author

Raz, Ran ; Shpilka, Amir ; Yehudayoff, Amir

Author_Institution

Weizmann Inst. of Sci., Rehovot

fYear

2007

fDate

21-23 Oct. 2007

Firstpage

438

Lastpage

448

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 Omega{n^4/3 log² n} The lower bound holds over any field.

Keywords

logic circuits; polynomials; rational functions; polynomial; rational functions; syntactically multilinear arithmetic circuits; Binary trees; Circuits; Computer science; Digital arithmetic; Mathematics; Polynomials; Radio access networks;

fLanguage

English

Publisher

ieee

Conference_Titel

Foundations of Computer Science, 2007. FOCS '07. 48th Annual IEEE Symposium on

Conference_Location

Providence, RI

ISSN

0272-5428

Print_ISBN

978-0-7695-3010-9

Type

conf

DOI

10.1109/FOCS.2007.13

Filename

4389514

Link To Document

https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2226508