Balancing syntactically multilinear arithmetic circuits

Ran Raz, Amir Yehudayoff

Research output: Contribution to journalArticle

35 Scopus citations

Abstract

In their seminal paper, Valiant, Skyum, Berkowitz and Rackoff proved that arithmetic circuits can be balanced. That is, they showed that for every arithmetic circuit Ψ of size s and degree r, there exists an arithmetic circuit Ψ of size poly (r, s) and depth O (log(r) log(s)) computing the same polynomial. In the first part of this paper, we follow the proof of Valiant el al. and show that syntactically multilinear arithmetic circuits can be balanced. That is, we show that if Φ is syntactically multilinear, then so is Ψ. Recently, a super-polynomial separation between multilinear arithmetic formula and circuit size was shown. In the second part of this paper, we use the result of the first part to simplify the proof of this separation. That is, we construct a (simpler) polynomial f (x 1, ... , x n ) such that Every multilinear arithmetic formula computing f is of size n Ω(log(n)). There exists a syntactically multilinear arithmetic circuit of size poly(n) and depth O(log2(n)) computing f.

Original languageEnglish (US)
Pages (from-to)515-535
Number of pages21
JournalComputational Complexity
Volume17
Issue number4
DOIs
StatePublished - Dec 1 2008
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Arithmetic circuits
  • Separation of circuit and formula size

Fingerprint Dive into the research topics of 'Balancing syntactically multilinear arithmetic circuits'. Together they form a unique fingerprint.

Cite this