Data Structure Lower Bounds and the Cell Probe Model – University of Copenhagen

Data Structure Lower Bounds and the Cell Probe Model

Talk by Kasper Green Larsen, Monday May 12 at 15.15-17.00


In this talk, I will first introduce and motivate the cell probe model for proving data structure lower bounds. The cell probe model is the most general model for proving data structure lower bounds and thus lower bounds proved in this model apply to essentially any imaginable data structure, in particular those developed in the most popular upper bound model, the word-RAM.

Unfortunately, this generality has come at a high cost: The strongest (static) lower bound proved to data, for any data structure problem, is only Omega(log m) where m is the number of different queries in the data structure problem. This barrier has not been exceeded, even for linear space data structures.

In the second half of the talk, I will shed light on this Omega(log m) barrier by demonstrating the previous techniques for proving static data structure lower bounds. I will start by describing Miltersen's reduction to communication complexity from 1995, yielding lower bounds peaking at Omega(log m / log S) where S is the space usage of the data structure. Unfortunately, this lower bound degenerates to Omega(1) for all problems with a polynomial number of queries (n^{O(1)} = S^{O(1)}) (which is true for most natural data structure problems). It took another 15 years before Patrascu and Thorup, in 2010, proved the first omega(1) lower bound for data structures with polynomially many queries. More precisely, their lower bound pushed the barrier to Omega(log m / log ((S log n) / n)), in particular giving lower bounds of Omega(log m / log log n) for space usage n log^{O(1)} n. Their improvement is based on a refined reduction to communication complexity, considering several queries in parallel. Finally, I will end the talk by introducing one of my own result from 2012, namely a technique - not based on communication complexity - which pushes the barrier slightly forward by giving lower bounds of Omega(log m / log(S/n)). Note that this peaks at Omega(log m) for linear space data structures.

About Kasper Green Larsen

Kasper Green Larsen is an Assistant Professor at the Department of Computer Science, Aarhus University. His main research area is data structures, with an emphasis on lower bounds and range searching. He obtained his Ph.D. in 2013 from Aarhus University, where some of his most notable results include the strongest lower bounds to date in both the cell probe and group model of computation as well as the fastest data structures for several fundamental problems in the area of geometric range searching. During his Ph.D. studies he earned a number of awards, including the STOC'12 Best Paper and Best Student Paper Award, the FOCS'11 Best Student Paper Award, a Google Europe Doctoral Fellowship and the Danish Minister of Science's EliteResearch (EliteForsk) travel scholarship.