loading...
 This Article 
   
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
2008 IEEE 23rd Annual Conference on Computational Complexity
Lower Bounds and Separations for Constant Depth Multilinear Circuits
June 22-June 26
ISBN: 978-0-7695-3169-4
ASCII Text
x 
 
Ran Raz, Amir Yehudayoff, "Lower Bounds and Separations for Constant Depth Multilinear Circuits," Computational Complexity, Annual IEEE Conference on, pp. 128-139, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008.
 
 
BibTex
x
 
@article{ 10.1109/CCC.2008.8,
author = {Ran Raz and Amir Yehudayoff},
title = {Lower Bounds and Separations for Constant Depth Multilinear Circuits},
journal ={Computational Complexity, Annual IEEE Conference on},
volume = {0},
year = {2008},
issn = {1093-0159},
pages = {128-139},
doi = {http://doi.ieeecomputersociety.org/10.1109/CCC.2008.8},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Computational Complexity, Annual IEEE Conference on
TI - Lower Bounds and Separations for Constant Depth Multilinear Circuits
SN - 1093-0159
SP128
EP139
A1 - Ran Raz,
A1 - Amir Yehudayoff,
PY - 2008
KW - Arithmetic Circuits
KW - Constant Depth
KW - Lower Bounds
KW - Separations
VL - 0
JA - Computational Complexity, Annual IEEE Conference on
ER -
 
We prove an exponential lower bound for the size of constant depth multilinear arithmetic circuits computing either the determinant or the permanent (a circuit is called multilinear, if the polynomial computed by each of its gates is multilinear). We also prove a super-polynomial separation between the size of product-depth 1 d and product-depth d+1 multilinear circuits (where d is constant). That is, there exists a polynomial f such that (1). There exists a multilinear circuit of product-depth d+1 and of polynomial size computing f. (2) Every multilinear circuit of product-depth d computing f has super-polynomial size.
Index Terms:
Arithmetic Circuits, Constant Depth, Lower Bounds, Separations
Citation:
Ran Raz, Amir Yehudayoff, "Lower Bounds and Separations for Constant Depth Multilinear Circuits," ccc, pp.128-139, 2008 IEEE 23rd Annual Conference on Computational Complexity, 2008
Usage of this product signifies your acceptance of the Terms of Use.