Algorithms and Complexity Seminar
Thursday, April 20, 2006, 4-5:15pm in 32-G575.
Data Structures and Cell Probe Complexity
Mihai Patrascu (MIT)
I will give an overview of techniques and open problems in cell-probe
complexity, as used to understand data structures. Data structures come
in two flavors, static and dynamic, requiring different lower bound
tools.
In the dynamic case, one uses epoch-based arguments pioneered by
Fredman and Saks [STOC'89], typically proving Omega(lg n/lglg n) lower
bounds. I will give a simple, self-contained proof in this framework.
Then, I will discuss more recent ideas that led to the first Omega(lg
n) lower bound. This is joint work with Erik Demaine [SODA'04, STOC'04]
and Corina Tarnita [ICALP'05].
In the static case, one typically uses communication complexity. I will
discuss the limitations of this approach, and then describe some ideas
used to prove the first lower bound which exceeds the communication
barrier. This is joint work with Mikkel Throup [STOC'06 and recent
manuscripts]. Finally, I will end with speculation on how progress on
static lower bounds can be used in the dynamic case.
Host: Madhu Sudan