Lower Bound Techniques for Data Structures

Place:
Department of Computer Science
University of Copenhagen
Universitetsparken
2100 Copenhagen O

Schedule and rooms:

Lecturers:
Mihai Patrascu (MIT)
Mikkel Thorup (AT&T)

Organisers:
Rasmus Pagh (pagh@itu.dk), David Pisinger (pisinger@diku.dk), Anna Östlin Pagh, Martin Zachariasen

Course description:
We will present the main recent and classic techniques for proving lower bounds for data structures. The field has seen exciting developments in
recent years, which led to excellent understanding of some central problems, and some very deep results about the organization of data on a
computer, such as:

* the first proven separation between linear and polynomial space

* binary trees are the optimal way for computing prefix sums

* classic search strategies like B-trees and van Emde Boas are often optimal

No background assumed. At the end of each session, there will be a discussion of relevant open problems, and student exercises will be provided for those interested.

Program
Thursday afternoon: dynamic data structures
* the chronogram technique: Omega(lg n / lglg n) lower bounds
* new approach for obtaining Omega(lg n) bounds
* applications to dynamic connectivity, partial sums
* mini-survey and open problems for dynamic graphs

Friday morning: static data structures and richness
* data structures and asymmetric communication complexity
* the richness method for communication lower bounds
* application to set disjointness
* reductions to Exact/Approximate Nearest Neighbor, Partial Match
* going above communication lower bounds: a better use of richness for near-linear space
* mini-survey and open problems for Nearest Neighbor problems

Friday afternoon: round elimination and variants
* round elimination and message compression
* applications to predecessor search
* beating communication complexity
* optimal bounds for predecessor search

Prerequisites:
No background assumed. At the end of each session, there will be a discussion of relevant open problems, and student exercises will be provided for those interested.

Exam:
No exam

Credits:
0 .5 ECTS points

Registration:
Please send an e-mail to <andreats@diku.dk>. No later than 20 July 2006

List of participants:
Philip Bille, IT-universitetet
Bjørn Petersen, Datalogisk Institut
Esben Rune Hansen, IT-universitetet
Peter Tidemann, IT-universitetet
Simon Spoorendonk (DIKU)
Martin Paluszewski (DIKU)
Benny Kjær Nielsen (DIKU)
Jens Egeblad (DIKU)
Fritz Henglein (DIKU)
Martin Zachariasen (DIKU)
Rasmus Pagh (ITU)
Thore Husfeldt (Lund)
Jyrki Katajainen (DIKU)
Emil Soelberg (DIKU)
Amr Elmasry, Alexandria University, Egypt
Claus Jensen (DIKU)

Notes from the lectures:
Note 1 (pdf)
Note 2 (pdf)
Note 3 (pdf)