๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Lower Bounds on the Depth of Monotone Arithmetic Computations

โœ Scribed by Don Coppersmith; Baruch Schieber

Publisher
Elsevier Science
Year
1999
Tongue
English
Weight
128 KB
Volume
15
Category
Article
ISSN
0885-064X

No coin nor oath required. For personal study only.

โœฆ Synopsis

dedicated to zvi galil's 50th birthday Consider an arithmetic expression of length n involving 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.5 log 2 n&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 2 log 2 n+O(1).

๐Ÿ“œ SIMILAR VOLUMES

An Exponential Lower Bound for the Size
An Exponential Lower Bound for the Size of Monotone Real Circuits
โœ Armin Haken; Stephen A. Cook ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 118 KB

We prove a lower bound, exponential in the eighth root of the input length, on the size of monotone arithmetic circuits that solve an NP problem related to clique detection. The result is more general than the famous lower bound of Razborov and Andreev, because the gates of the circuit are allowed t

Further results on the lower bounds of m
Further results on the lower bounds of mean color numbers
โœ F. M. Dong ๐Ÿ“‚ Article ๐Ÿ“… 2004 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 181 KB ๐Ÿ‘ 1 views

Let G be a graph with n vertices. The mean color number of G, denoted by (G), is the average number of colors used in all n-colorings of G. This paper proves that (G) ! (Q), where Q is any 2-tree with n vertices and G is any graph whose vertex set has an ordering x 1 ,x 2 , . . . ,x n such that x i