The complexity of parallel prefix problems on small domains

Chaudhuri, Shiva P. ; Radhakrishnan, Jaikumar (1997) The complexity of parallel prefix problems on small domains Information and Computation, 138 (1). pp. 1-22. ISSN 0890-5401

Full text not available from this repository.

Official URL: http://www.sciencedirect.com/science/article/pii/S...

Related URL: http://dx.doi.org/10.1006/inco.1997.2654

Abstract

We establish non-trivial lower bounds for several prefix problems in the CRCW PRAM model. The chaining problem is, given a binary input, for each 1 in the input, to find the index of the nearest 1 to its left. Our main result is that for an input ofnbits, solving the chaining problem usingO(n) processors requires inverse-Ackerman time. This matches the previously known upper bound. We also give a reduction to show that the same lower bound applies to a parenthesis matching problem, again matching the previously known upper bound. We also give reductions to show that similar lower bounds hold for the prefix maxima and the range maxima problem.

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
ID Code:89532
Deposited On:27 Apr 2012 14:17
Last Modified:27 Apr 2012 14:17

Repository Staff Only: item control page