A Cell Probe Lower Bound for the Predecessor Search Problem in PRAM

We study the predecessor search problem in the classical PRAM model of computation. In this problem, the input is a set of n ℓ-bit integers and the goal is to store the input in a data structure of size S(n) such that given a query value q, the predecessor of q can be found efficiently. This is a very classical problem with an extensive history.

We prove a lower bound for this problem in the strongest CRCW PRAM model. A simplified version of the lower bound states that in a K-processor PRAM model with O(log n)-bit registers, the query requires Ω(log K log n) worst-case time under the realistic setting where the space is near-linear.