6.851: Advanced Data Structures Spring 2007

In the last lecture we considered the problem of finding the predecessor in its static version. We also introduced the idea of communication complexity and message elimination to prove lower bounds. In this lecture we present some ideas that refine the method of message elimination and make it possible to prove even tighter lower bounds. 2 Problem Description and Lower Bounds In the static predecessor problem we have n integers that fit in a word size w and the set representation takes s = n2 a space. Then we have the following lower bound: logB n logw n w − lg n ⎪ ⎨ lg a max lg w/a a lg lg n lg w/a ⎪ ⎩ lg lg w lg