Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR08-006 | 18th January 2008 00:00

Lower Bounds and Separations for Constant Depth Multilinear Circuits

RSS-Feed




TR08-006
Authors: Ran Raz, Amir Yehudayoff
Publication: 8th February 2008 05:45
Downloads: 3482
Keywords: 


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-depth $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.



ISSN 1433-8092 | Imprint