Data Structures and Cell Probe Complexity
Speaker: Mihai Patrascu , MIT CSAIL
Date: April 20 2006
Time: 4:00PM to 5:15PM
Location: 32-G575
Host: Madhu Sudan, MIT CSAIL
Contact: Joanne Hanley, 617.253.6054, joanne@csail.mit.edu
Relevant URL: http://theory.csail.mit.edu/~madhu/algcomp/mihai-abs.html
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.
See other events that are part of Algorithms and Complexity Spring 2006
See other events happening in April 2006
