Tuesday, 1:30am-2:20pm in EE1 045.

TIME: 1:30-2:20 pm,  Feb 28, 2006

PLACE: EE1 045

TITLE: Cell-Probe Complexity and Predecessor Search

SPEAKER:  Mihai Patrascu
          MIT

ABSTRACT:
I will begin with an overview of cell-probe complexity, as used to understand
data structures. I will touch both on dynamic problems, including advances
from recent years, and static problems.

Then I will describe a recent (STOC'06) progress in the static case. In joint
work with Mikkel Thorup, we showed the first cell-probe lower bound which is
higher than the communication complexity, thus breaking a long-standing barrier.
Our technique proves the first separation between polynomial and near-linear
space, and gives tight bounds for the well-studied predecessor problem.