Lower bounds and separations for constant depth multilinear circuits

Ran Raz, Amir Yehudayoff

Research output: Chapter in Book/Report/Conference proceedingConference 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-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.

Original languageEnglish (US)
Title of host publicationProceedings - 23rd Annual IEEE Conference on Computational Complexity, CCC 2008
Pages128-139
Number of pages12
DOIs
StatePublished - Sep 23 2008
Externally publishedYes
Event23rd Annual IEEE Conference on Computational Complexity, CCC 2008 - College Park, MD, United States
Duration: Jun 23 2008Jun 26 2008

Publication series

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

Other

Other23rd Annual IEEE Conference on Computational Complexity, CCC 2008
CountryUnited States
CityCollege Park, MD
Period6/23/086/26/08

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Lower bounds and separations for constant depth multilinear circuits'. Together they form a unique fingerprint.

  • Cite this

    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 (pp. 128-139). [4558817] (Proceedings of the Annual IEEE Conference on Computational Complexity). https://doi.org/10.1109/CCC.2008.8