Lower bounds and separations for constant depth multilinear circuits

Ran Raz; Amir Yehudayoff

doi:10.1109/CCC.2008.8

Lower bounds and separations for constant depth multilinear circuits

Ran Raz, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

16 Scopus citations

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 • 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.

Original language	English (US)
Title of host publication	Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Pages	128-139
Number of pages	12
DOIs	https://doi.org/10.1109/CCC.2008.8
State	Published - 2008
Externally published	Yes
Event	23rd Annual IEEE Conference on Computational Complexity, CCC 2008 - College Park, MD, United States Duration: Jun 23 2008 → Jun 26 2008

Publication series

Name	Proceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)	1093-0159

Other

Other	23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Country/Territory	United States
City	College Park, MD
Period	6/23/08 → 6/26/08

All Science Journal Classification (ASJC) codes

Software
Theoretical Computer Science
Computational Mathematics

Access to Document

10.1109/CCC.2008.8

Cite this

@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",

}

Raz, R & Yehudayoff, A 2008, Lower bounds and separations for constant depth multilinear circuits. in Proceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008., 4558817, Proceedings of the Annual IEEE Conference on Computational Complexity, pp. 128-139, 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, College Park, MD, United States, 6/23/08. https://doi.org/10.1109/CCC.2008.8

TY - GEN

T1 - Lower bounds and separations for constant depth multilinear circuits

AU - Raz, Ran

AU - Yehudayoff, Amir

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 -

Lower bounds and separations for constant depth multilinear circuits

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this