Matthew A Grayson
Journal of Complexity
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). © 1999 Academic Press.
Matthew A Grayson
Journal of Complexity
Ligang Lu, Jack L. Kouloheris
IS&T/SPIE Electronic Imaging 2002
Ruixiong Tian, Zhe Xiang, et al.
Qinghua Daxue Xuebao/Journal of Tsinghua University
Ziv Bar-Yossef, T.S. Jayram, et al.
Journal of Computer and System Sciences