TY - GEN
T1 - Lower bounds and separations for constant depth multilinear circuits
AU - Raz, Ran
AU - Yehudayoff, Amir
N1 - Copyright:
Copyright 2008 Elsevier B.V., All rights reserved.
PY - 2008
Y1 - 2008
N2 - 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-depth1 d and product-depth d+1 multilinear circuits (where d is constant). That is, there exists a polynomial f such that • There exists a multilinear circuit of pro duct-depth d+1 and of polynomial size computing f. • Every multilinear circuit of product-depth d computing f has super-polynomial size.
AB - 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-depth1 d and product-depth d+1 multilinear circuits (where d is constant). That is, there exists a polynomial f such that • There exists a multilinear circuit of pro duct-depth d+1 and of polynomial size computing f. • Every multilinear circuit of product-depth d computing f has super-polynomial size.
UR - http://www.scopus.com/inward/record.url?scp=51949118452&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=51949118452&partnerID=8YFLogxK
U2 - 10.1109/CCC.2008.8
DO - 10.1109/CCC.2008.8
M3 - Conference contribution
AN - SCOPUS:51949118452
SN - 9780769531694
T3 - Proceedings of the Annual IEEE Conference on Computational Complexity
SP - 128
EP - 139
BT - Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
T2 - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Y2 - 23 June 2008 through 26 June 2008
ER -