Lower bounds on the depth of monotone arithmetic computations

Don Coppersmith, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

Abstract

Consider an arithmetic expression of lengthninvolving only the operations {+,×} and non-negative constants. We prove lower bounds on the depth of any binary computation tree over the same sets of operations and constants that computes such an expression. We exhibit a family of arithmetic expressions that requires computation trees of depth at least 1.5log2n-O(1), thus proving a conjecture of S. R. Kosaraju (1986,in"Proc. of the 18th ACM Symp. on Theory Computing," pp. 231-239). In contrast, Kosaraju showed how to compute such expressions with computation trees of depth 2log2n+O(1).

Original languageEnglish (US)
Pages (from-to)17-29
Number of pages13
JournalJournal of Complexity
Volume15
Issue number1
DOIs
StatePublished - Mar 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Algebra and Number Theory
  • Statistics and Probability
  • Numerical Analysis
  • General Mathematics
  • Control and Optimization
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Lower bounds on the depth of monotone arithmetic computations'. Together they form a unique fingerprint.

Cite this