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 -