Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
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.
Vladimir Yanovski, Israel A. Wagner, et al.
Ann. Math. Artif. Intell.
T. Graham, A. Afzali, et al.
Microlithography 2000
Matthew A Grayson
Journal of Complexity
Heinz Koeppl, Marc Hafner, et al.
BMC Bioinformatics