Lower bounds on the depth of monotone arithmetic computations

Abstract

Consider an arithmetic expression of length n involving only the operations (+,) and non-negative constants. The authors prove lower bounds on the depth of any binary computation tree over the same set of operations and constants that computes such an expression. In their main result they exhibit a family of arithmetic expressions that requires computation trees of depth at least 1.5 log2n-O(1). The authors also consider the family of arithmetic expressions defined by alternating 5-3 trees. For this family they show a tight bound of 5/(log215)log2n+O(1) on the depth of any computation tree. This is the best known tight bound for any family of arithmetic expressions.