Lower bounds for predecessor searching in the cell probe model

We consider a fundamental problem in data structures, static predecessor searching: Given a subset S of size n from the universe [m], store S so that queries of the form "What is the predecessor of x in S?" can be answered efficiently. We study this problem in the cell probe model introduced by Yao [1981]. Recently, Beame and Fich [2002] obtained optimal bounds on the number of probes needed by any deterministic query scheme if the associated storage scheme uses only n^O(1) cells of word size (log m)^O(1) bits. We give a new lower bound proof for this problem that matches the bounds of Beame and Fich. Our lower bound proof has the following advantages: it works for randomised query schemes too, while Beame and Fich\´s proof works for deterministic query schemes only. In addition, it is simpler than Beame and Fich\´s proof. We prove our lower bound using the round elimination approach of Miltersen, Nisan, Safra and Wigderson [1998]. Using tools from information theory, we prove a strong round elimination lemma for communication complexity that enables us to obtain a tight lower bound for the predecessor problem. We also use our round elimination lemma to obtain a rounds versus communication tradeoff for the \´greater-than\´ problem, improving on the tradeoff in [1998]. We believe that our round elimination lemma is of independent interest and should have other applications.