loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07)
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
Providence, Rhode Island
October 21-October 23
ISBN: 0-7695-3010-9
ASCII Text
x 
 
Ran Raz, Amir Shpilka, Amir Yehudayoff, "A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits," Foundations of Computer Science, Annual IEEE Symposium on, pp. 438-448, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/FOCS.2007.13,
author = {Ran Raz and Amir Shpilka and Amir Yehudayoff},
title = {A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits},
journal ={Foundations of Computer Science, Annual IEEE Symposium on},
volume = {0},
year = {2007},
issn = {0272-5428},
pages = {438-448},
doi = {http://doi.ieeecomputersociety.org/10.1109/FOCS.2007.13},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Foundations of Computer Science, Annual IEEE Symposium on
TI - A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits
SN - 0272-5428
SP438
EP448
A1 - Ran Raz,
A1 - Amir Shpilka,
A1 - Amir Yehudayoff,
PY - 2007
KW - null
VL - 0
JA - Foundations of Computer Science, Annual IEEE Symposium on
ER -
 
We construct an explicit polynomial f(x_1 , \ldots ,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 ^2 n). The lower bound holds over any field.
Citation:
Ran Raz, Amir Shpilka, Amir Yehudayoff, "A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits," focs, pp.438-448, 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.