@inproceedings{79cb0e8af35b4e0eab2984bdbc6e9081,

title = "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.",

author = "Don Coppersmith and Baruch Schieber",

year = "1992",

month = jan,

day = "1",

doi = "10.1109/SFCS.1992.267763",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "288--295",

booktitle = "Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992",

address = "United States",

note = "33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 ; Conference date: 24-10-1992 Through 27-10-1992",

}