Lower bounds on the depth of monotone arithmetic computations
Don Coppersmith, Baruch Schieber
FOCS 1992
The all nearest smaller values problem is defined as follows. Let A = (a1, a2, an) be n elements drawn from a totally ordered domain. For each ai, 1 ≤ i ≤ n, find the two nearest elements in A that are smaller than ai (if such exist): the left nearest smaller element aj (with j < i) and the right nearest smaller element ak (with k > i). We give an O(log log n) time optimal parallel algorithm for the problem on a CRCW PRAM. We apply this algorithm to achieve optimal O(log log n) time parallel algorithms for four problems: (i) Triangulating a monotone polygon, (ii) Preprocessing for answering range minimum queries in constant time, (iii) Reconstructing a binary tree from its inorder and either preorder or postorder numberings, (vi) Matching a legal sequence of parentheses. We also show that any optimal CRCW PRAM algorithm for the triangulation problem requires Ω(log log n) time. © 1993 Academic Press, Inc.
Don Coppersmith, Baruch Schieber
FOCS 1992
Allan Borodin, Prabhakar Raghavan, et al.
Journal of the ACM
Allan Borodin, Prabhakar Raghavan, et al.
STOC 1993
Dan Gusfield, Gad M. Landau, et al.
Information Processing Letters