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.
内容简介：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.