DocumentCode :
2226508
Title :
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(x1,..., xn), with coefficients in {0, 1}, such that the size of any syntactically multilinear arithmetic circuit computing f is at least Omega{n4/3 log2 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.ricest.ac.ir/dl/search/defaultta.aspx?DTC=49&DC=2226508
بازگشت