Optimal Bounds for Predecessor Search and the First Separation between Linear and Polynomial Space

Speaker: Mikkel Thorup

Abstract:

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 determine the optimal query time for any combination of space and word size w. In particular, we show that the classic van Emde Boas search time of O(log w) cannot be improved, even if we allow randomization. This is a separation from polynomial space, since Beame and Fich [STOC'99] give a predecessor search time of O(log w / log log w) using quadratic space.