6.897: Advanced Data Structures Spring 2005

In the last lecture we used round elimination to prove lower bounds for the static predecessor problem in the cell probe model. We showed a lower bound of Ω(min{lga w, lgb n}) on the number of probes required to solve the problem, where a = O(lg space(n)), the number of bits to index the data structure, and b = w, the number of bits returned by a single cell probe. For a polynomial size data structure, this implies that when lg n lg lg n = lg 2 w, some problem instances require Ω( lg w lg lg w) = Ω( lg n lg lg n) probes. The bound lgw n is matched by fusion trees, but van Emde Boas achieves lg w per query, which does not match lga w. In this lecture we show upper and lower bounds of Θ(min{lgw n, 2 An O( lg w lg