Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR97-008 | 16th March 1997 00:00

Pointer Jumping Requires Concurrent Read


Authors: Noam Nisan, Ziv Bar-Yossef
Publication: 17th March 1997 09:24
Downloads: 964


We consider the well known problem of determining the k'th
vertex reached by chasing pointers in a directed graph of
out-degree 1. The famous "pointer doubling" technique
provides an O(log k) parallel time algorithm on a
Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that
this problem requires Omega(k) steps on an Exclusive-Read
Exclusive-Write (EREW) PRAM, for every k < (c sqrt(log n)),
where n is the number of vertices and c is a constant.

This yields a boolean function which can be computed in
O(log log n) time on a CREW PRAM, but requires
Omega(sqrt (log n)) time on even an `ideal' EREW PRAM. This
is the first separation known for boolean functions between the
power of EREW and CREW PRAMs. Previously, separations between
EREW and CREW PRAMs were only known for functions on `huge'
input domains, or for restricted types of EREW PRAMs.

ISSN 1433-8092 | Imprint