Speaker: Mikkel Thorup University
Time: 2007-06-07 14:00-2007-06-07 15:00
Venue: AT&T Labs--Research, Shannon Laboratory

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.

Short Bio:

   Mikkel Thorup is a Lead Member of Technical Staff at AT&T Labs-Research where he has been since 1998. He holds a PhD from Oxford University from 1993. From 1993 to 1998 he was at the faculty of University of Copenhagen. Thorup's main work is in Algorithms and Data Structures and he is the editor of this area for Journal of the ACM. Currently he also serves on the editorial boards of SIAM Journal on Computing, ACM Transactions on Algorithms, and the open access journal Theory of Computing. Thorup has more than a hundred refereed publications and he is a co-inventor of the Smart Sampling Technologies that lie at the hart of AT&T's Scaleable Traffic Analysis Service. 
     Thorup is a Fellow of the ACM, a Member of the Royal Danish Academy of Sciences, and an Adjunct Full Professor at the University of Copenhagen.