Data Structure Lower Bounds 1/3

552 views · Published 14 March 2016 · 40:56 · Indexed 8 November 2026

Channel: Institut Henri Poincaré · 2016 · Science & Technology

Watch on YouTube

By Kasper Green Larsen (Aarhus University)
Abstract: In this mini-course, we survey the various techniques developed for proving data structure lower bounds. On the dynamic data structures side, we cover the Chronogram Technique of Fredman and Saks for proving [Math Processing Error] lower bounds, the Information Transfer technique of Patrascu and Demaine for proving logn lower bounds, and the mixture of the Chronogram technique and Cell Sampling technique introduced by Larsen for proving [Math Processing Error] lower bounds. On the static data structures side, we first see Miltersen et al.'s reduction to communication complexity, resulting in [Math Processing Error] lower bounds. We then see the refined reduction by Patrascu and Thorup for proving [Math Processing Error] lower bounds and finally we see the Cell Sampling technique first introduced by Panigrahy et al. and later refined by Larsen to prove [Math Processing Error] lower bounds.

More from this channel