Computer Science/Discrete Mathematics Seminar III

We develop a new technique for proving cell-probe lower bounds for static data structures. Previous lower bounds used a reduction to communication games, which was known not to be tight by counting arguments. We give the first lower bound for an explicit problem which breaks this communication complexity barrier. In addition, our bounds give the first separation between polynomial and near linear space. Such a separation is inherently impossible by communication complexity. Using our lower bound technique and new upper bound constructions, we obtain tight bounds for searching predecessors among a static set of integers. We get tight bounds for any combination of word length w, space s, and number of integers n in the static set. In particular, we show that the classic data structure of van Emde Boas [FOCS'75], searching in O(lg w) time, is tight for near-linear space. This should be contrasted with the O(lg w/lglg w) search time obtained with quadratic space by Beame and Fich [STOC'99]. Beame and Fich proved their bound optimal for polynonimial space and asked what happened with near-linear space.