@inproceedings{106fafa96c8f484a82bc303808065a17,

title = "Lower bounds and separations for constant depth multilinear circuits",

abstract = "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.",

author = "Ran Raz and Amir Yehudayoff",

year = "2008",

doi = "10.1109/CCC.2008.8",

language = "English (US)",

isbn = "9780769531694",

series = "Proceedings of the Annual IEEE Conference on Computational Complexity",

pages = "128--139",

booktitle = "Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008",

note = "23rd Annual IEEE Conference on Computational Complexity, CCC 2008 ; Conference date: 23-06-2008 Through 26-06-2008",

}