Lower bounds and sparations for constant depth multilinear circuits

Ran Raz, Amir Yehudayoff

Research output: Contribution to journalArticle

71 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 product-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)
Pages (from-to)171-207
Number of pages37
JournalComputational Complexity
Volume18
Issue number2
DOIs
StatePublished - Jun 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Mathematics(all)
  • Computational Theory and Mathematics
  • Computational Mathematics

Keywords

  • Arithmetic circuits
  • Constant depth circuits
  • Separations

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

  • Cite this