On the depth complexity of formulas

Eli Shamir, Marc Snir

Research output: Contribution to journalArticlepeer-review


The problem of minimizing the depth of formulas by equivalence preserving transformations is formalized in a general algebraic setting. For a particular algebraic system ∑0 specific methods of a dynamic programming nature are developed for proving lower bounds on depth. Such lower bounds for ∑0 automatically imply the same results for the systems of (i) arithmetic computations with addition and multiplication only, and (ii) computations over finite languages using union and concatenation. The specific lower bounds obtained are (i) depth 2 n-o(n) for the permanent, (ii) depth (0.25+o(1))log2n for the symmetric polynomials and (iii) depth 1.16log n for a problem of formula size n.

Original languageEnglish (US)
Pages (from-to)301-322
Number of pages22
JournalMathematical Systems Theory
Issue number1
StatePublished - Dec 1979
Externally publishedYes

ASJC Scopus subject areas

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


Dive into the research topics of 'On the depth complexity of formulas'. Together they form a unique fingerprint.

Cite this